题目描述
leetcode 中等题
给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。
字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
- 例如， “ace” 是 “abcde” 的子序列。
示例1：
1
2
3
| 输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
|
示例2：
1
2
| 输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2
|
提示1：
1
2
3
4
| 1 <= s.length <= 5 * 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。
|
分桶 + 二分查找 （贪心）
最容易想到的方法就是对于每个 $word$ ，通过双指针的方法和 $s$ 进行匹配，指针 $i$ 和 $j$ 初始时分别指向 $word$ 和 $a$ 的第 $0$ 位字符，如果匹配成功则将两个指针分别向后移动，否则只移动 $j$，如果 $i$ 能匹配结束的话则 $ans$ 加一。
但是该方法在该题的数据规模下会 TLE，所以需要进行优化。
一种方法是我们可以将 $s$ 按照每个字符进行分桶，每个桶内存储该字符在 $s$ 内从小到大排列后的索引值。那么对于每个 $word$ 我们都会进行一轮遍历，每一轮都独立维护一个 $next$ 值，并在每次 $i$ 指针后移时，尝试通过二分查找得到当前 $i$ 所指向字符的对应桶内第一个大于 $next$ 的索引值（贪心思路，目的是让每次的 $next$ 都尽量小），然后将 $next$ 更新为该索引值，过程中若不存在大于 $next$ 的索引值则匹配失败，若能匹配结束则 $ans$ 加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map<Character, List<Integer>> map = new HashMap<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
List<Integer> list = map.computeIfAbsent(c, ArrayList::new);
list.add(i);
map.put(c, list);
}
int ans = 0;
for(int i = 0; i < words.length; i++){
char[] item = words[i].toCharArray();
int next = Integer.MIN_VALUE;
boolean flag = true;
for(int j = 0; j < item.length; j++){
List<Integer> list = map.getOrDefault(item[j], new ArrayList<>());
int left = 0, right = list.size();
while(left < right){
int mid = left + right >> 1;
if(list.get(mid) <= next){
left = mid + 1;
}else if(list.get(mid) > next){
right = mid;
}
}
if(left < list.size()){
next = list.get(left);
}else{
flag = false;
break;
}
}
if(flag){
ans++;
}
}
return ans;
}
}
|
类似上面的思路，我们也可以对于每个 $word$ 进行逆序遍历，只需要在二分查找时改成找到第一个小于 $i$ 的索引值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| class Solution {
public int numMatchingSubseq(String s, String[] words) {
Map<Character, List<Integer>> map = new HashMap<>();
for(int i = 0; i < s.length(); i++){
char c = s.charAt(i);
List<Integer> list = map.computeIfAbsent(c, ArrayList::new);
list.add(i);
map.put(c, list);
}
int ans = 0;
for(int i = 0; i < words.length; i++){
char[] item = words[i].toCharArray();
int next = Integer.MAX_VALUE;
boolean flag = true;
for(int j = item.length - 1; j >=0; j--){
List<Integer> list = map.getOrDefault(item[j], new ArrayList<>());
int left = 0, right = list.size();
while(left < right){
int mid = left + right >> 1;
if(list.get(mid) < next){
left = mid + 1;
}else if(list.get(mid) >= next){
right = mid;
}
}
if(left - 1 >= 0 && left - 1 < list.size()){
next = list.get(left - 1);
}else{
flag = false;
break;
}
}
if(flag){
ans++;
}
}
return ans;
}
}
|
分桶 + 多指针
上面的做法的思路是对 $s$ 按字符进行分桶，从而加速每一个 $word$ 与 $s$ 之间的匹配速度，相当于每个 $word$ 都会独立匹配一次。
而另一种做法的思路是将 $s$ 同时与所有 $word$ 进行匹配。具体来说每一个 $word$ 都有着独立的指针 $i$ ，并且初始值为 0，那么对每一个 $word$ 按照当前匹配到的字符，也就是各自 $i$ 指针指向的字符进行分桶。那么我们就可以直接遍历 $s$，每次只需要将 $j$ 所指向字符的对应桶内的所有 $word$ 拿出来并将它们的 $i$ 指针往后移动一位，然后重新维护桶即可，而若当前取出的 $word$ 对应的 $i$ 已经到达结尾，则 $ans$ 加一。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| class Solution {
public int numMatchingSubseq(String s, String[] words) {
Queue<int[]>[] bucket = new Queue[26];
for (int i = 0; i < 26; ++i) {
bucket[i] = new ArrayDeque<int[]>();
}
for (int i = 0; i < words.length; ++i) {
bucket[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});
}
int ans = 0;
for (int i = 0; i < s.length(); ++i) {
char c = s.charAt(i);
int size = bucket[c - 'a'].size();
while (size > 0) {
int[] item = bucket[c - 'a'].poll();
if (item[1] == words[item[0]].length() - 1) {
++ans;
} else {
++item[1];
bucket[words[item[0]].charAt(item[1]) - 'a'].offer(item);
}
--size;
}
}
return ans;
}
}
|