792. 匹配子序列的单词数（难度：中等）

题目连接：https://leetcode.cn/problems/number-of-matching-subsequences/

题目描述：

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

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

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

示例 1:

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

Example 2:

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

提示:

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

解法一：二分查找

我们可以利用一个二维数组，统计出来，s中每个字符对应的下标都有哪些。然后在通过遍历words时，每一个word的每一个字符，是否在二维数组中找到，并且其下标也是递增。

优化：需要将每次在字符对应的数组中查找下标的过程，使用二分查找。

代码：

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        int result = 0;
        List<Integer>[] dp = new List[26];

        for (int i = 0; i < 26; i++) {
            dp[i] = new ArrayList<>();
        }

        for (int i = 0; i < s.length(); i++) {
            dp[s.charAt(i) - 'a'].add(i);
        }

        for (String word : words) {
            int t = -1;
            boolean flag = false;
            for (char c : word.toCharArray()) {
                List<Integer> integers = dp[c - 'a'];
                if(integers.isEmpty() || integers.get(integers.size() - 1) <= t) {
                    flag = false;
                    break;
                }
                t = binartSearch(integers,t);
                flag = true;
            }
            if (flag) {
                result++;
            }
        }
        return result;
    }
    
    public int binartSearch(List<Integer> list,int target) {
        int left = 0,right = list.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if(list.get(mid) > target) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }
        return list.get(left);
    }
}

解法二：分桶

我们也可以根据 words 的首字符进行分桶，我们遍历字符串s，每遍历一个字符，将首字符是该字符的单词下标向后移动一位，如果word下标移动到了结尾，就在最终结果加一。

代码：

class Solution {
    public int numMatchingSubseq(String s, String[] words) {
        Deque<int[]>[] d = new Deque[26];
        for (int i = 0; i < 26; ++i) {
            d[i] = new ArrayDeque<>();
        }
        for (int i = 0; i < words.length; ++i) {
            d[words[i].charAt(0) - 'a'].offer(new int[] {i, 0});
        }
        int ans = 0;
        for (char c : s.toCharArray()) {
            Deque<int[]> q = d[c - 'a'];
            for (int t = q.size(); t > 0; --t) {
                int[] p = q.pollFirst();
                int i = p[0], j = p[1] + 1;
                if (j ==  words[i].length()) {
                    ++ans;
                } else {
                    d[words[i].charAt(j) - 'a'].offer(new int[] {i, j});
                }
            }
        }
        return ans;
    }
}