792.匹配子序列的单词数

链接：792.匹配子序列的单词数
难度：Medium
标签：字典树、数组、哈希表、字符串、二分查找、动态规划、排序
简介：给定字符串 s 和字符串数组 words, 返回 words[i] 中是 s 的子序列的单词个数 。

题解 1 - cpp

• 编辑时间：2022-11-17
• 执行用时：184ms
• 内存消耗：50.2MB
• 编程语言：cpp
• 解法介绍：把 s 的每个坐标存入后，进行二分。

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>& words) {
        vector<vector<int>> list(26);
        for (int i = 0; i < s.size(); i++) list[s[i] - 'a'].push_back(i);
        int ans = 0;
        for (auto &word : words) {
            if (word.size() > s.size()) continue;
            int p = -1;
            bool f = true;
            for (auto &c : word) {
                auto &ilist = list[c - 'a'];
                auto it = upper_bound(ilist.begin(), ilist.end(), p);
                if (it == ilist.end()) {
                    f = false;
                    break;
                }
                if (!f) break;
                p = *it;
            }
            if (f) ans++;
        }
        return ans;
    }
};