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.

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