LeetCode-792. 匹配子序列的单词数【字典树，哈希表，二分查找】

题目描述：

给定字符串 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 * 10^4
1 <= words.length <= 5000
1 <= words[i].length <= 50
words[i]和 s 都只由小写字母组成。

https://leetcode.cn/problems/number-of-matching-subsequences/

解题思路一：以字母开头存储每个words[i]，然后依次处理。

比如对于 words = [“a”, “bb”, “acd”, “ace”]，我们得到以下的分桶结果：

a: [“a”, “acd”, “ace”]
b: [“bb”]
然后我们从 s 的第一个字符开始遍历，假设当前字符为 ‘a’，我们从 ‘a’ 开头的桶中取出所有单词。对于取出的每个单词，如果此时单词长度为 1，说明该单词已经匹配完毕，我们将答案加 1；否则我们将单词的首字母去掉，然后放入下一个字母开头的桶中，比如对于单词 “acd”，去掉首字母 ‘a’ 后，我们将其放入 ‘c’ 开头的桶中。这一轮结束后，分桶结果变为：

c: [“cd”, “ce”]
b: [“bb”]
遍历完 s 后，我们就得到了答案。

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<queue<string>> d(26);//桶
        for (auto& w:words) d[w[0]-'a'].emplace(w);
        int ans = 0;
        for (char& c : s) {
            auto& q=d[c-'a'];
            int size=q.size();
            whiel(size--){//处理对应的桶
                auto t = q.front();q.pop();                
                if (t.size()==1) ++ans;
                else d[t[1]-'a'].emplace(t.substr(1));
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：$O(n+{\sum }_{i=0}^{m-1}\mid w_i\mid )$
空间复杂度：O(m)
其中 n 和 m 分别为 s 和 words 的长度，而|wi∣为 words[i] 的长度。

解题思路二：实际上，每个桶可以只存储单词的下标i以及该单词当前匹配到的位置j，这样可以节省空间。

就是将原来字母开头的一个数组，里面的字符串变为一个数字。

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<queue<pair<int, int>>> d(26);
        for (int i=0;i<words.size();++i) d[words[i][0]-'a'].emplace(i, 0);
        int ans=0;
        for (char& c : s) {
            auto& q=d[c-'a'];
            int size=q.size();
            while(size--){
                auto [i, j] = q.front();q.pop();                
                if (++j==words[i].size()) ++ans;//这里无论如何都会执行一个++j操作。
                else d[words[i][j]-'a'].emplace(i,j);
            }
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

时间复杂度：$O(n+{\sum }_{i=0}^{m-1}\mid w_i\mid )$
空间复杂度：O(m)
其中 n 和 m 分别为 s 和 words 的长度，而|wi∣为 words[i] 的长度。

解题思路三：二分查找。数组d里面记录s中26个英文字母的下标。然后依次遍历每个words[i]，在d里面二分查找，找不到说明不是子序列。

class Solution {    
public:    
    int numMatchingSubseq(string s, vector<string>& words){  
        vector<vector<int>> d(26);      
        for (int i=0;i<s.size();++i) d[s[i]-'a'].emplace_back(i);
        int ans=0;
        auto check=[&](string& w){
            int i=-1;
            for (char& c:w) {
                auto& t=d[c-'a'];
                int j=upper_bound(t.begin(), t.end(), i) - t.begin();
                if (j==t.size()) return false;
                i=t[j];
            }
            return true;
        };
        for (auto& w:words) ans+=check(w);
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

时间复杂度：$O(n+{\sum }_{i=0}^{m-1}\mid w_i\mid )$
空间复杂度：O(n)
其中 n 和 m 分别为 s 和 words 的长度，而|wi∣为 words[i] 的长度。
参考链接