一、题目
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
例如， “ace” 是 “abcde” 的子序列。
二、示例
2.1> 示例 1:
【输入】 s = "abcde", words = ["a","bb","acd","ace"] 【输出】 3 【解释】 有三个是 s 的子序列的单词: "a", "acd", "ace"。
2.2> 示例 2:
【输入】 s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"] 【输出】 2
提示:
- •
1<= s.length <=5 * 10^4 - •
1<= words.length <=5000 - •
1<= words[i].length <=50 - •
words[i]和s都只由小写字母组成。
三、解题思路
根据题目描述，需要我们去words字符串数组中却判断，哪些是字符串s的子序列，最后再将子序列的总个数返回回来。那么，对于字符串子序列，我们主要关心如下两点：
【是否存在？】子序列中的某个字符是否在字符串s中存在。 【顺序对吗？】子序列中字符出现的顺序是否违背了字符串s中的顺序。
那么针对这两种关注点，我们首先遍历字符串s中的每个字符，由于这些字符都是由小写字母构成，所以我们可以通过采用：字符减去‘a’来确定下标位置，并将该字符在s中出现的位置保存到ArrayList集合中。
然后，我们再分别遍历字符串数组words中的每个字符串，逐一判断每个字符出现的位置顺序是否与s相同，如果不同，则可以判断该字符串不是s的子序列。具体操作详情请见下图：
四、代码实现
代码语言：javascript复制class Solution {
public int numMatchingSubseq(String s, String[] words) {
List<Integer>[] sm = new ArrayList[26]; // index：字符 sm[index]：字符出现的位置集合
char[] sc = s.toCharArray();
for (int i = 0; i < sc.length; i ) {
if (sm[sc[i]-'a'] == null) sm[sc[i]-'a'] = new ArrayList<>();
sm[sc[i]-'a'].add(i);
}
int result = words.length; // 初始化result数量为所有单词，如果不满足条件，则陆续执行减1操作
for (String word : words) { // 遍历每个单词
int compareIndex = -1, index;
for (int i = 0; i < word.length(); i ) { // 遍历每个字符
if (sm[word.charAt(i)-'a'] == null ||
((index = findCharIndex(compareIndex, sm[word.charAt(i)-'a'])) <= compareIndex)) {
result--;
break;
}
compareIndex = index;
}
}
return result;
}
// 折半查找
private int findCharIndex(int compareIndex, List<Integer> list) {
int head = 0, tail = list.size() - 1, mid;
while (head < tail) {
mid = head (tail - head) / 2;
if (list.get(mid) > compareIndex) tail = mid;
else head = mid;
}
return list.get(head);
}
}
