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.