匹配子序列问题

匹配子序列问题

lc792. 匹配子序列的单词数

给定字符串 s 和字符串数组 words, 返回 words[i] 中是s的子序列的单词个数 。

字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。

• 例如， “ace” 是 “abcde” 的子序列。

示例 1:

输入: s = "abcde", words = ["a","bb","acd","ace"]
输出: 3
解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
1
2
3

Example 2:

输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
输出: 2
1
2

提示:

• 1 <= s.length <= 5 * 104
• 1 <= words.length <= 5000
• 1 <= words[i].length <= 50
• words[i]和 s 都只由小写字母组成。

暴力法

用到一个Map判断数量限制和字符限制

再加双指针判断位置顺序

class Solution {
    Map<Character, Integer> map_init = new HashMap<>();
    Map<Character, Integer> map2 = new HashMap<>();
    public int numMatchingSubseq(String s, String[] words) {
        //不能单纯用Map 要考虑顺序
        //预处理 统计s的字符及数量
        for(char c : s.toCharArray()){
            map_init.put(c,map_init.getOrDefault(c,0) + 1);
        }
        int res = 0;
        for(String t : words){
            //预处理
            map2.clear();
            for(char c : t.toCharArray()){
                map2.put(c,map2.getOrDefault(c,0) + 1);
            }
            if(isValid(s,t,map2)) res++;
        }
        return res;
    }
    //判断t是不是s的子序列 双指针法
    public boolean isValid(String s, String t, Map<Character, Integer> map2){
        //先判断数量和字母是否符合
        //map2有的 map_init都要有且map_init>=map2
        for(Character key : map2.keySet()){
            if(map_init.getOrDefault(key, 0) < map2.get(key)) return false;
        }
        //再判断顺序双指针移动法
        int i = 0; //长的
        int j = 0;  //短的
        while(i < s.length() && j < t.length()){
            if(t.charAt(j) == s.charAt(i)){
                j++;
            }
            i++;
        }
        return j == t.length();
    }
}
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

遗憾超时…

分桶法

class Solution {
    //分桶法 桶：双向队列
    public int numMatchingSubseq(String s, String[] words) {
        Deque<String>[] deques = new Deque[26];
        for(int i = 0; i < 26; i++){
            deques[i] = new ArrayDeque<>();
        }
        //每个单词根据首字母入桶
        for(String t : words){
            deques[t.charAt(0) - 'a'].add(t);
        }
        int res = 0;
        //遍历字符串s
        for(char c : s.toCharArray()){
            Deque<String> d = deques[c - 'a'];
            for(int k = d.size(); k > 0; k--){
                String cur = d.pollFirst();
                if(cur.length() == 1){
                    res++;
                }else{
                    deques[cur.charAt(1) - 'a'].offer(cur.substring(1));
                }
            }
            //注意下面是错误的写法，对于bb这样的重复的测试用例 起不到分桶的效果
            // while(d.size() > 0){
            //     String cur = d.pollFirst();
            //     if(cur.length() == 1){
            //         System.out.print(cur +' ');
            //         res++;
            //     }else{
            //         deques[cur.charAt(1) - 'a'].offer(cur.substring(1));
            //     }
            // }
        }
        return res;
    }
}
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

哈希+二分

class Solution {
    List[] d = new List[26]; 
    public int numMatchingSubseq(String s, String[] words) {
        //方法2：哈希表+二分查找
        //哈希表存储s的首字母的下标位置
        //通过二分查找curWord当前字母在s中的index是否符合要求（要求：后一个的index不能小于前一个）
        //预处理
        for(int i = 0; i < 26; i++){
            d[i] = new ArrayList<>();
        }
        for(int i = 0; i < s.length(); i++){
            d[s.charAt(i) - 'a'].add(i);
        }
        int res = 0;
        for(String w : words){
            if(check(w)) res++;
        }
        return res;
    }
    public boolean check(String w){
        int index = -1;
        for(int k = 0; k < w.length(); k++){
            int c = w.charAt(k) - 'a';
            int j = binarySearch(d[c],index);
            if(j == d[c].size()) return false;
            index = d[c].get(j);
        }
        return true;
    }
    //index:前一个字母遍历到的位置
    //返回在index后面的首字母为要求的list下标
    //如果下标为list.size() 那就表明没找到
    //找到就更新index
    public int binarySearch(List list, int index){
        int l = 0, r = list.size();
        while(l < r){
            int mid = (l + r) >> 1;
            if(list.get(mid) > index){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}
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
42
43
44
45
46