<p>Given a string <code>s</code> and an array of strings <code>words</code>, return <em>the number of</em> <code>words[i]</code> <em>that is a subsequence of</em> <code>s</code>.</p>

<p>A <strong>subsequence</strong> of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.</p>

<ul>
	<li>For example, <code>&quot;ace&quot;</code> is a subsequence of <code>&quot;abcde&quot;</code>.</li>
</ul>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;abcde&quot;, words = [&quot;a&quot;,&quot;bb&quot;,&quot;acd&quot;,&quot;ace&quot;]
<strong>Output:</strong> 3
<strong>Explanation:</strong> There are three strings in words that are a subsequence of s: &quot;a&quot;, &quot;acd&quot;, &quot;ace&quot;.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> s = &quot;dsahjpjauf&quot;, words = [&quot;ahjpjau&quot;,&quot;ja&quot;,&quot;ahbwzgqnuk&quot;,&quot;tnmlanowax&quot;]
<strong>Output:</strong> 2
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>
	<li><code>1 &lt;= words.length &lt;= 5000</code></li>
	<li><code>1 &lt;= words[i].length &lt;= 50</code></li>
	<li><code>s</code> and <code>words[i]</code> consist of only lowercase English letters.</li>
</ul>

class Solution {
public:
    // function to check if a given word is a subsequence of string s
    bool isSubsequence(string s, string word) {
    // Edge case: if the length of s is less than the length of word, return false
    if(s.length() < word.length()) return false;
    int sIndex = 0, wIndex = 0; // sIndex and wIndex are pointers for s and word respectively
    
    // iterate through both s and word
    while(sIndex < s.length() && wIndex < word.length()) {
        // if s[sIndex] is equal to word[wIndex], increment both pointers
        if(s[sIndex] == word[wIndex]) {
            sIndex++;
            wIndex++;
        } else {
            sIndex++;
        }
    }
    
    // if wIndex reaches the end of word, it means it is a subsequence of s
    return (wIndex == word.length());
}

int numMatchingSubseq(string s, vector<string>& words) {
    int matchCount = 0; // variable to keep track of the number of matching subsequences
    
    unordered_map<string, int> dp; // hash map to store previously checked words and their result
    
    // iterate through all words in the given vector
    for(auto &word : words) {
        // if the word has already been checked, add the result to matchCount
        if(dp.find(word) != dp.end()) {
            matchCount += dp[word];
        } else {
            // if the word has not been checked yet, check it and add the result to matchCount
            matchCount += dp[word] = isSubsequence(s, word);
        }
    }
    return matchCount;
    }
};
340429