> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/string/792.-number-of-matching-subsequences.md).

# 792. Number of Matching Subsequences

Given string `S` and a dictionary of words `words`, find the number of `words[i]` that is a subsequence of `S`.

```
Example :
Input: 
S = "abcde"
words = ["a", "bb", "acd", "ace"]
Output: 3
Explanation: There are three words in words that are a subsequence of S: "a", "acd", "ace".
```

**Note:**

* All words in `words` and `S` will only consists of lowercase letters.
* The length of `S` will be in the range of `[1, 50000]`.
* The length of `words` will be in the range of `[1, 5000]`.
* The length of `words[i]` will be in the range of `[1, 50]`.

```cpp
// Optimized Brute Force with Hashset
int numMatchingSubseq(string S, vector<string>& words) { // time: O(words_len * S_len); space: O(words_len)
    int res = 0, n = S.length();
    unordered_set<string> valid, invalid;
    for (string word : words) {
        if (valid.count(word) || invalid.count(word)) {
            if (valid.count(word)) ++res;
            continue;
        }
        // Use two pointers to check
        int i = 0, j = 0, m = word.length();
        while (i < n && j < m) {
            if (word[j] == S[i]) ++j;
            ++i;
        }
        if (j == m) {
            ++res;
            valid.insert(word);
        } else invalid.insert(word);
    }
    return res;
}
```

```cpp
// Binary Search
int numMatchingSubseq(string S, vector<string>& words) { // time: O(words_len * average str_len * log(S_len)); space: O(S_len)
    // Build a lookup index table
    vector<vector<int> > idx(26);
    for (int i = 0; i < S.length(); ++i) idx[S[i] - 'a'].push_back(i);
    int res = 0;
    for (const string& word : words) {
        int prev = -1;
        bool found = true;
        for (char c : word) {
            auto it = upper_bound(idx[c - 'a'].begin(), idx[c - 'a'].end(), prev);
            if (it == idx[c - 'a'].end()) {
                found = false;
                break;
            } else prev = *it;
        }
        if (found) ++res;
    }
    return res;
}
```

```cpp
bool isSubsequence(const string& S, const string& word) {
    int idx = -1;
    for (char ch : word) {
        idx = S.find(ch, idx + 1);
        if (idx == -1) return false;
    }
    return true;
}
int numMatchingSubseq(string S, vector<string>& words) {
    int res = 0;
    for (const string& word : words) {
        if (isSubsequence(S, word)) ++res;
    }
    return res;
}
```