# LeetCode 792. Number of Matching Subsequences

## Description:

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

## 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].

## 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”.

## Solution:

class Solution {
public:
int numMatchingSubseq(string S, vector<string>& words) {

int counter = 0;
for (const auto &word : words) {
auto wordSize = word.size();
size_t match = static_cast<size_t>(-1);
size_t index = 0;
do {
match = S.find(word[index], match + 1);
if (match == string::npos) {
break;
}
++index;
} while (index < wordSize);

if (index == wordSize) {
++counter;
}
}

return counter;
}
};


Using an index to denote the position where the letter of words[i] appears in S, and sequentially find the next letter of words[i] in S. If there are a letter that is not found, then words[i] is not a subsequence of S. Note that std::string::find is used here, but directly using loops would be faster.