匹配子序列的个数的算法 c++

C++中有两种方法可以解决给定字符串`s`匹配一组子序列（words）的数量问题：

**方法一：分桶优化法 (时间复杂度O(nm))[^1]**

class Solution {
public:
    int numMatchingSubseq(string s, vector<string>&& words) {
        vector<queue<string>> d(26); // 分桶依据单词首字母
        for(const auto &w : words) d[w[0] - 'a'].enqueue(w);

        int res = 0;
        for(char &c : s) { 
            auto &q = d[c - 'a'];
            while(!q.empty()) {
                auto t = q.front();
                q.dequeue();
                if(t.size() == 1) res++; // 如果字符匹配，计数加一
                else d[t[1] - 'a'].enqueue(t.substr(1));
            }
        }
        return res;
    }
};

在这个方法中，我们把每个单词按照第一个字符分组，然后遍历`s`，每次从对应桶中取出一个子串，如果当前字符匹配，就递减子串长度，直到遇到非空子串。

**方法二：朴素暴力法 (时间复杂度O(n*m*words.size()))**

class Solution {
public:
    bool isSubseq(string &s, string subS) {
        for(int i = 0, j = 0; i < s.size(); i++) {
            if(s[i] == subS[j]) {
                j++;
                if(j == subS.size()) return true;
            }
        }
        return false;
    }

    int numMatchingSubseq(string s, vector<string>&& words) {
        int res = 0;
        for(int i = 0; i < words.size(); i++) {
            if(isSubseq(s, words[i])) res++;
        }
        return res;
    }
};

这个方法更简单，但效率较低，因为它对于每一个`words`中的子串，都会独立地在`s`中进行逐字符的比较。