力扣(LeetCode)792. 匹配子序列的单词数(C++)

二分查找

直观思考，本题可以将 $words$ 中每个单词 $word$ 依次和目标字符串 $s$ 比较，检查是否为子串。时间复杂度 $n\times {\sum }_{i=0}^{m-1}word{s}_i$ $n$ 是 $s$ 的长度, $m$ 是 $words$ 的长度，问题规模 $10^{11}$ , $TLE$ 。

注意到， $s$ 中只有 $26$ 个字母 ， 类比哈希思想分桶，但是桶内键值对不唯一，就可以二分优化了。 $alpha[i]$ 存储 $i$对应字母 的所有下标，那么 $alpha$ 就存储了 $26$ 个字母对应 $s$ 的下标。只需一次遍历 $s$ ，即可得到 $alpha$ 。

二分如下：遍历所有单词 $word$ ，遍历单词的字母 $c$ ，记录位置 $p$ ，表示 $c$ 在目标串 $s$ 中的位置，二分查找桶中第一个大于 $p$ 的位置 $it$ ， 如果找到，则令 $p$ 等于这个位置，可以继续匹配 ; 如果查找越界，说明桶中没有足够字母，可行解- -，提前 $break$。

代码展示

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>> alpha(26);
        for(int i = 0;i<s.size();i++) alpha[s[i]-'a'].emplace_back(i);//存所有s字母的下标//分了26个桶
        int ans = words.size();//初始认为所有word符合条件
        for(auto &word:words){//遍历words
            if(word.size()>s.size()){//剪枝
                ans--;
                continue;
            }
            int p = -1;//初始小于所有数//找第一个字符
            for(auto &c:word){
                auto &pos = alpha[c-'a'];//桶
                auto it = upper_bound(pos.begin(),pos.end(),p);//桶中第一个大于p的位置
                if(pos.end()==it){//查无此字母
                    ans--;
                    break;//剪枝
                }
                p = it[0];//下标更新
            }
        }
        return ans;
    }
};
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

博主致语

理解思路很重要！
欢迎读者在评论区留言，作为日更博主，看到就会回复的。

AC

复杂度分析

1. 时间复杂度: $O(logn\times {\sum }_{i=0}^{m-1}word{s}_i)$， $n$ 是 $s$ 的长度, $m$ 是 $words$ 的长度。
2. 空间复杂度: $O(n)$，$alpha$ 保存了 $s$ 所有字母的下标， $alpha$ 的空间复杂度 $O(n)$ 。