题目：

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

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

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

示例 1:

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

Example 2:

1
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 都只由小写字母组成。

解题思路：

一开始没仔细读题，以为匹配子序列就是字符出现次数一样，我直接写了一个哈希，然后就wa了一发。。。

哈希表 + 二分查找

题目所说的匹配子序列的意思是，删除掉一些字符，然后words中的字符类型数量要 <= s 中的字符类型数量，并且顺序不能反。

1
2
3
"abcde"
"ace" 是 "abcde" 的子序列
"aec" 不是 "abcde" 的子序列，因为"aec" 的e和c在 s 中顺序是 ce

那么我们既要保证顺序不会乱，又要保证数量对，我第一个想到的就是哈希表，key-> list 。

Python 的 collections 里的 defaultdict，然后使用 bisect_right 库使用的是c实现的二分查找，比自己写的要快。

代码：

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        from collections import defaultdict
        from bisect import bisect_right
        idx = defaultdict(list)
        ans = 0

        for i, c in enumerate(s):
            idx[c].append(i)

        for word in words:
            p = -1
            for c in word:
                j = bisect_right(idx[c], p)
                if j == len(idx[c]):
                    break
                p = idx[c][j]
            else:
                ans += 1

        return ans

C++

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, vector<string> &words) {
        vector<vector<int>> pos(26);
        for (int i = 0; i < s.size(); ++i) {
            pos[s[i] - 'a'].push_back(i);
        }
        int res = words.size();
        for (auto &w : words) {
            if (w.size() > s.size()) {
                --res;
                continue;
            }
            int p = -1;
            for (char c : w) {
                auto &ps = pos[c - 'a'];
                auto it = upper_bound(ps.begin(), ps.end(), p);
                if (it == ps.end()) {
                    --res;
                    break;
                }
                p = *it;
            }
        }
        return res;
    }
};