Number of Matching Subsequences LeetCode solution in Python

1
# Runtime: 851 ms (Top 55.45%) | Memory: 16.4 MB (Top 32.26%)
2
class Solution:
3
    def numMatchingSubseq(self, s: str, words: List[str]) -> int:
4
        word_dict = defaultdict(list)
5
        numMatch = 0
6
        # add words into bucket with key as order of the first letter
7
        for w in words:
8
            word_dict[ord(w[0]) - ord("a")].append(w)
9
        # loop through the characters in s
10
        for c in s:
11
            qualified = word_dict[ord(c) - ord("a")]
12
            word_dict[ord(c) - ord("a")] = []
13
            for q in qualified:
14
                # if the word starts with the specified letter. i.e this is the last letter of the word
15
                if len(q) == 1:
16
                    numMatch += 1
17
                else:
18
                    word_dict[ord(q[1]) - ord("a")].append(q[1:])
19
        return numMatch