# 792. Number of Matching Subsequences

#### Medium

***

Given a string `s` and an array of strings `words`, return *the number of* `words[i]` *that is a subsequence of* `s`.

A **subsequence** 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.

* For example, `"ace"` is a subsequence of `"abcde"`.

 

**Example 1:**

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

**Example 2:**

```
Input: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
Output: 2
```

 

**Constraints:**

* `1 <= s.length <= 5 * 104`
* `1 <= words.length <= 5000`
* `1 <= words[i].length <= 50`
* `s` and `words[i]` consist of only lowercase English letters.

```python
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        result = []
        for word in words:
            if self.isSubsequence(word, s):
                result.append(word)
        return len(result)
    
    @lru_cache
    def isSubsequence(self, s: str, t: str) -> bool:
        if not s:
            return True
        index = 0
        for j in range(len(t)):
            if s[index] == t[j]:
                index += 1
            if index == len(s):
                return True
        return False
```