[LeetCode] Number of Matching Subsequence

leetcode

This problem is similar to LeetCode - Is Subsequence.
However, we cannot use the same method because this time we have multiple strings to compare at
the same time. And if we do use the same method it would result in TLE.
Therefore, we can utilize hash map to compare all the words at the same time.

We go through S and for each character we see if it’s also in words.
And then we can slice the word string so that it only contains the rest of the string.
Once a word is empty string we know that all its characters are found in S, and thus it is S’s subsequence. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def numMatchingSubseq(self, S, words):
        """
        :type S: str
        :type words: List[str]
        :rtype: int
        """
        d = collections.defaultdict(list)
        ans = 0
        for w in words:
            d[w[0]].append(w[1:])
        for s in S:
            wait = []
            if s in d:
                while len(d[s]) > 0:
                    w = d[s].pop()
                    if len(w) == 0: ans += 1
                    else: wait.append(w)
                for w in wait:
                    d[w[0]].append(w[1:])
        return ans