LeetCode_多指针_二分搜索_中等_792.匹配子序列的单词数

1.题目

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

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

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

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

示例 2：
输入: s = “dsahjpjauf”, words = [“ahjpjau”,“ja”,“ahbwzgqnuk”,“tnmlanowax”]
输出: 2

提示：
1 <= s.length <= 5 * 10⁴
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/number-of-matching-subsequences

2.思路

（1）直接判断子序列
如果直接判断数组 words 中的每个 word 是否为 s 的子序列，其判断方法可参考LeetCode_双指针_二分搜索_简单_392.判断子序列这篇文章，该文章中提供了双指针法和二分搜索法来进行判断。但是使用双指针法在 LeetCode 中提交时会出现“超出时间限制”的提示！

（2）多指针
思路参考本题官方题解。

双指针法中是每一个单词分别和字符串 s 进行匹配，这样对于每一次匹配都需要从头开始遍历字符串 s，这增加了额外的时间开销。所以我们考虑将字符串数组 words 中的全部字符串和字符串 s 同时进行匹配——同样对于每一个需要匹配的字符串我们用一个指针来指向它需要匹配的字符，那么在遍历字符串 s 的过程中，对于当前遍历到的字符如果有可以匹配的字符串，那么将对应的字符串指针往后移动一单位即可。那么当字符串 s 遍历结束时，字符串数组中全部字符串的匹配情况也就全部知道了。

3.代码实现（Java）

//思路1————判断子序列
//双指针法
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int res = 0;
        int n = words.length;
        int sLen = s.length();
        for (String word : words) {
            if (isSubsequence(word, s)) {
                res++;
            }
        }
        return res;
    }

    //判断 s 是否为 t 的子序列，如果是则返回 true，否则返回 false
    public boolean isSubsequence(String s, String t) {
    	//双指针法
        int i = 0;
        int j = 0;
        int sLen = s.length();
        int tLen = t.length();
        while (i < sLen && j < tLen) {
            if (s.charAt(i) == t.charAt(j)) {
                i++;
            }
            j++;
        }
        return i == sLen;
    }
}

//二分搜索法
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        List<Integer>[] pos = new List[26];
        for (int i = 0; i < 26; ++i) {
            pos[i] = new ArrayList<Integer>();
        }
        for (int i = 0; i < s.length(); ++i) {
            pos[s.charAt(i) - 'a'].add(i);
        }
        int res = words.length;
        for (String w : words) {
            if (w.length() > s.length()) {
                --res;
                continue;
            }
            int p = -1;
            for (int i = 0; i < w.length(); ++i) {
                char c = w.charAt(i);
                if (pos[c - 'a'].isEmpty() || pos[c - 'a'].get(pos[c - 'a'].size() - 1) <= p) {
                    --res;
                    break;
                }
                p = binarySearch(pos[c - 'a'], p);
            }
        }
        return res;
    }

    public int binarySearch(List<Integer> list, int target) {
        int left = 0, right = list.size() - 1;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (list.get(mid) > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return list.get(left);
    }
}
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

//思路2————多指针
class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Queue<int[]>[] queue = new Queue[26];
        for (int i = 0; i < 26; i++) {
            queue[i] = new ArrayDeque<int[]>();
        }
        for (int i = 0; i < words.length; i++) {
            queue[words[i].charAt(0) - 'a'].offer(new int[]{i, 0});
        }
        int res = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            int len = queue[c - 'a'].size();
            while (len > 0) {
                int[] t = queue[c - 'a'].poll();
                if (t[1] == words[t[0]].length() - 1) {
                    res++;
                } else {
                    t[1]++;
                    queue[words[t[0]].charAt(t[1]) - 'a'].offer(t);
                }
                len--;
            }
        }
        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