---
tags: leetcode
---

# [792. Number of Matching Subsequences](https://leetcode.com/problems/number-of-matching-subsequences/)
---
# My Solution
## Solution 1: Brute force (TLE)
### The Key Idea for Solving This Coding Question
### C++ Code

class Solution {
public:
    int numMatchingSubseq(string s, vector<string> &words) {
        int substrCnt = 0;

        for (auto &word : words) {
            if (word.size() <= s.size() && isSubstr(s, word)) {
                ++substrCnt;
            }
        }

        return substrCnt;
    }

private:
    bool isSubstr(string &s, string &word) {
        int i = 0, j = 0;
        while (i < s.size() && j < word.size()) {
            if (s[i] == word[j]) {
                ++i;
                ++j;
            } else {
                ++i; // Delete s[i] from s.
            }
        }

        // case 1: i >= s.size() && j < word.size()  ==> return false
        // case 2: i < s.size() && j >= word.size()  ==> return true
        // case 3: i >= s.size() && j >= word.size() ==> return true
        if (i >= s.size() && j < word.size()) {
            return false;
        }
        return true;
    }
};

### Time Complexity
$O(m \cdot n)$
$m$ is the number of words in `words`.
$n$ is the length `s`.
### Space Complexity
$O(1)$
## Solution 2: Binary search

class Solution {
public:
    int numMatchingSubseq(string s, vector<string> &words) {
        unordered_map<char, vector<int>> charToIdx;
        for (int i = 0; i < s.size(); ++i) {
            charToIdx[s[i]].push_back(i);
        }

        int substrCnt = 0;

        for (auto &word : words) {
            if (word.size() <= s.size() && isSubstr(charToIdx, s.size(), word)) {
                ++substrCnt;
            }
        }

        return substrCnt;
    }

private:
    bool isSubstr(unordered_map<char, vector<int>> &charToIdx, int sLen, string &word) {
        int sIdx = 0, wordIdx = 0;
        while (sIdx < sLen && wordIdx < word.size()) {
            auto iter = charToIdx.find(word[wordIdx]);
            if (iter == charToIdx.end()) {
                return false;
            }

            // Use binary search to find an index in indices
            // that is greater than or equal to sIdx.
            vector<int> &indices = iter->second;
            int left = 0, right = indices.size() - 1;
            while (left < right) {
                int middle = left + (right - left) / 2;
                if (indices[middle] < sIdx) {
                    left = middle + 1;
                } else {
                    right = middle;
                }
            }

            if (indices[left] < sIdx) {
                return false;
            }
            sIdx = indices[left] + 1;
            ++wordIdx;
        }

        if (sIdx >= sLen && wordIdx < word.size()) {
            return false;
        }
        return true;
    }
};

### Time Complexity
$O(m \cdot logn)$
$m$ is the number of words in `words`.
$n$ is the length of `s`.
### Space Complexity
$O(n)$
# Miscellane
<!--
# Test Cases

"abcde"
["a","bb","acd","ace"]

"dsahjpjauf"
["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]

"btovxbkumc"
["btovxbku","to","zueoxxxjme","yjkclbkbtl"]

"dsahpjaufj"

["ahjpjau","ja","ahbwzgqnuk","tnmlanowax","hpjau"]

* Wrong Answer:
https://leetcode.com/submissions/detail/560708232/testcase/
* TLE:
https://leetcode.com/submissions/detail/706071682/testcase/
* TLE:
https://leetcode.com/submissions/detail/706706684/testcase/
* TLE:
https://leetcode.com/submissions/detail/713312545/testcase/
-->