792. Number of Matching Subsequences

Problem Link

Description

---

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.

Solution

---

Python3

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        mp = collections.defaultdict(collections.deque)
        
        for w in words:
            mp[w[0]].append(w)
        
        res = 0
        
        for c in s:
            n = len(mp[c])
            
            for _ in range(n):
                word = mp[c].popleft()
                if len(word) == 1:
                    res += 1
                else:
                    mp[word[1]].append(word[1:])
        
        return res