Number of Valid Words for Each Puzzle LeetCode solution in Python

1
class Solution:
2
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
3
        look_up = collections.defaultdict(int)
4

5
        def get_mask(word):
6
            mask = 0
7
            for c in word:
8
                mask |= 1 << (ord(c) - ord("a"))
9
            return mask
10

11
        for word in words:
12
            mask = get_mask(word)
13
            look_up[mask] += 1
14
        ans = []
15

16
        def solve(puzzle_idx, mask, c_idx):
17
            if c_idx == len(puzzles[puzzle_idx]):
18
                ans[-1] += look_up[mask]
19
                return
20
            # take this c_idx
21
            solve(
22
                puzzle_idx,
23
                mask | 1 << (ord(puzzles[puzzle_idx][c_idx]) - ord("a")),
24
                c_idx + 1,
25
            )
26
            # dont take this c_idx
27
            solve(puzzle_idx, mask, c_idx + 1)
28

29
        for i, puzzle in enumerate(puzzles):
30
            ans.append(0)
31
            solve(i, 1 << (ord(puzzle[0]) - ord("a")), 1)
32
        return ans