792. 匹配子序列的单词数

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

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

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

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

题目链接

哈希表 52/53

很容易想到可以使用哈希表去存储S里面字符的下标。map<int,vector<int>>。用数组将下标全部存储起来，就能得到一个，该字符出现下标的单调增序列。然后，我们去记录每一个能大于前一个出现字符下标的最小下标即可。

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int cnt=0;
        map<char,vector<int>>dict;
        for(int i=0;i<s.size();i++){
            dict[s[i]].push_back(i);
        }
        for(auto word:words){
            int num=-1;
            int flag;
            for(int i=0;i<word.size();i++){
                flag=0;
                if(dict.count(word[i])){
                    for(int j=0;j<dict[word[i]].size();j++){
                        if(dict[word[i]][j]>num){
                            num=dict[word[i]][j];
                            flag=1;
                            break;
                        }
                    }
                }
                else{
                    break;
                }

                if(!flag){
                    break;
                }
            }
            if(flag)
                cnt++;
        }
        return cnt;
    }
};

二分+哈希（ac）

不加优化的做法卡了第52个样例，全是a。将记录前一个满足最小下标部分由顺序查找换成二分查找即可

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        int cnt=0;
        map<char,vector<int>>dict;
        for(int i=0;i<s.size();i++){
            dict[s[i]].push_back(i);
        }
        for(auto word:words){
            int num=-1;
            int flag;
            for(int i=0;i<word.size();i++){
                flag=0;
                if(dict.count(word[i])){
                    int j = upper_bound(dict[word[i]].begin(), dict[word[i]].end(), num) - dict[word[i]].begin();
                    if(j==dict[word[i]].size()) break;
                    num=dict[word[i]][j];
                    flag=1;
                }
                else{
                    break;
                }
                if(!flag){
                    break;
                }
            }
            if(flag)
                cnt++;
        }
        return cnt;
    }
};