给定字符串 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]。
算法分析
由于S的长度可以达到50000，如果对于每个words[k]都搜索一遍字符串S显然会导致算法低效。思路是：对于字符串S的每个字符，用哈希表保存每个字符出现的所有位置，对于words中的某个子串，先在哈希表搜索第一个字符确定子序列的起始位置，之后根据这个字符在字符串S的位置 i 搜索下一个字符在S的位置 j （二分查找），要求有 j > i。需要注意如果某个words子串存在连续重复的字符需要作特殊处理。
代码
class Solution{
public static int numMatchingSubseq(String S
, String
[] words
) {
Map
<Character
, ArrayList
<Integer>> map
= new HashMap<>();
int count
= 0;
for(int i
= 0; i
< S
.length(); i
++) {
char c
= S
.charAt(i
);
if(!map
.containsKey(c
))
map
.put(c
, new ArrayList<Integer>(S
.length()));
map
.get(c
).add(i
);
}
outer
:
for(String e
: words
) {
int preIndex
= -1;
for(int i
= 0; i
< e
.length(); i
++) {
char c
= e
.charAt(i
);
if(!map
.containsKey(c
))
continue outer
;
ArrayList
<Integer> temp
= map
.get(c
);
if(i
== 0) {
preIndex
= temp
.get(0);
}else {
int indexOfTemp
= Collections
.binarySearch(temp
, preIndex
);
if(indexOfTemp
>= 0) {
indexOfTemp
++;
if(indexOfTemp
>= temp
.size())
continue outer
;
preIndex
= temp
.get(indexOfTemp
);
} else {
indexOfTemp
= -indexOfTemp
- 1;
if(indexOfTemp
>= temp
.size())
continue outer
;
preIndex
= temp
.get(indexOfTemp
);
}
}
}
count
++;
}
return count
;
}
}
