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

• 题目描述：
• 解题思路一：以字母开头存储每个words[i]，然后依次处理。
• 解题思路二：实际上，每个桶可以只存储单词的下标i以及该单词当前匹配到的位置j，这样可以节省空间。
• 解题思路三：二分查找。数组d里面记录s中26个英文字母的下标。然后依次遍历每个words[i]，在d里面二分查找，找不到说明不是子序列。

题目描述：

给定字符串 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& words) {vector> 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;}
};

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

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

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

class Solution {
public:int numMatchingSubseq(string s, vector& words) {vector>> d(26);for (int i=0;iauto& 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;}
};

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

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

class Solution {    
public:    int numMatchingSubseq(string s, vector& words){  vector> d(26);      for (int i=0;iint 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;}
};

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