Problem 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:

1
2
3
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:

1
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:

We don’t want to check each word one by one. So the idea is to cache every word’s starting character to dictionary. When we walk through the s, we find all the candidate that starts with the s[i].

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        res = 0
        dic = defaultdict(list)
        # put every word's starting character to dictionary
        # walk through every character to find the candidate
        
        for word in words:
            dic[word[0]].append(word)
        
        for c in s:
            candidate = dic[c]
            dic[c] = [] # we used this character, empty this to empty
            for word in candidate:
                if len(word) == 1:
                    res += 1
                else:
                    dic[word[1]].append(word[1:])
        return res

time complexity: $O()$
space complexity: $O()$
reference:
related problem: