Skip to main content

792. Number of Matching Subsequences

https://leetcode.com/problems/number-of-matching-subsequences/

Python​

Trie with BFS​

class Solution:
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
        trie = dict()
        for word_id in range(len(words)):
            word = words[word_id]
            cur = trie
            for letter in word:
                cur = cur.setdefault(letter, {})
            if '#' not in cur:
                cur['#'] = set()
            cur["#"].add(word_id) # Use index as word id, since the words might have duplicate item
        
        hits = set()
        queue = [(trie, 0)]
        
        # BFS search from the subsequence of 's'
        while queue:
            node, i = queue.pop()
            for letter in node:
                if letter == '#':
                    hits |= node['#']
                else:
                    for j in range(i, len(s)):
                        if s[j] == letter:
                            queue.append((node[letter], j+1))
                            break
        return len(hits)