题目大意：
匹配子序列的单词数
给定字符串 S 和单词字典 words, 求 words[i] 中是 S 的子序列的单词个数。
示例: 输入: S = "abcde" words = ["a", "bb", "acd", "ace"] 输出: 3 解释: 有三个是 S 的子序列的单词: "a", "acd", "ace"。
注意:
- 所有在words和 S 里的单词都只由小写字母组成。
- S 的长度在 [1, 50000]。
- words 的长度在 [1, 5000]。
- words[i]的长度在[1, 50]。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=792
解题思路分析：
个人感觉这道中等题目的难度略微偏高。解题时，我们需要使用每个字典中的单词去和S比较，看它是否是S的子序列。不过这种比较非常耗费时间，因此我们需要对S进行一下预处理。首先定义一个二维数组arr[][]，其中 arr[i][j]代表距离S中第i位字符最近的j字符的位置。换句话说，我们需要遍历一边字符串，记录下字符串S每一位上的字符，在它右侧距离它最近的a-z分别在哪。
做好预处理之后，我们使用字典中的每一个单词与arr进行比较。首先定义2个下标分别表示当前单词的下标index，以及S中对应的下标indexAtS。我们通过 arr[indexAtS][index]可以判断出距离S当前下标之后最近的index所指向的字符位置，如果位置为0，说明 indexAtS 之后不存在该字符（indexAtS 之后的下标一定大于0），退出继续比较下一个单词。如果存在， indexAtS 赋值为 arr[indexAtS][index]，同时 index 加一，继续寻找下一个字符，直到所有字符都存在为止，此时找到一个合理子序列，返回结果加一。
另外上述逻辑有一个小漏洞，如果当前单词的首字符与S的首字符相同，那么在第一次调用arr[indexAtS][index]时，可能无法得到正确答案。详细处理可以参照代码：
public int numMatchingSubseq(String S, String[] words) {
// 预处理用的数组
int[][] arr = new int[S.length()][26];
// 预处理
for(int i=S.length()-2;i>=0;i--){
arr[i]=Arrays.copyOf(arr[i+1],26);
arr[i][S.charAt(i+1)-'a']=i+1;
}
// 比较每一个单词
int res=0;
for(String s : words){
// 对应S的下标
int indexAtS=0;
// 当前单词下标
int index=0;
// 如果当前单词首字符等于S首字符
if(s.charAt(0)==S.charAt(0)){
// 当前单词下标加一
index++;
// 如果当前单词长度只有1，说明当前单词已经遍历结束，结果加一
if(s.length()==1) res++;
}
// 继续比较单词接下来的字符，在S中是否存在
while(index<s.length()){
// 当前字符
int c=s.charAt(index)-'a';
// 如果indexAtS之后不存在c，当前单词不合法
if(arr[indexAtS][c]==0) break;
// 将indexAtS更新为c在S中的位置
indexAtS=arr[indexAtS][c];
// index加一
// 如果index为单词最后一位，代表单词中所有字符均在S中找到
if(++index==s.length()) res++;
}
}
return res;
}本题解法执行时间为81ms。
Runtime: 81 ms, faster than 60.45% of Java online submissions for Number of Matching Subsequences.
Memory Usage: 58.4 MB, less than 12.50% of Java online submissions for Number of Matching Subsequences.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-792-number-of-matching-subsequences-解题思路分析/