aboutsummaryrefslogtreecommitdiff
path: root/num_valid_words_puzzle.py
blob: 72198252eca55ce3e3cae3fde1bbc7425337bcd6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
# 1178. Number of Valid Words for Each Puzzle

"""
with respect to a given puzzle string, a word is valid of both the following
conditions are satisfied. word contains the first letter of puzzle. for each
letter in word, that letter is in puzzle. invalid words are "beefed" (does
not include "a") and "based" (includes "s" which is not in the puzzle).
return an array where arr[i] is the number of words in the given word list
words that is valid with respect to the puzzle
"""


class Solution(object):
    def get_mask(self, word):
        mask = 0
        for c in word:
            i = ord(c) - ord("a")
            mask |= 1 << i
        return mask

    def findNumOfValidWords(self, words, puzzles):
        """
        :type words: List[str]
        :type puzzles: List[str]
        :rtype: List[int]
        """
        freq = {}
        for w in words:
            mask = self.get_mask(w)
            freq[mask] = freq.get(mask, 0) + 1
        ans = [0] * len(puzzles)
        for i in range(len(puzzles)):
            p = puzzles[i]
            mask = self.get_mask(p)
            sub_mask = mask
            total = 0
            bit_idx = ord(p[0]) - ord("a")
            while True:
                if sub_mask >> bit_idx & 1:
                    total += freq.get(sub_mask, 0)
                if not sub_mask:
                    break
                sub_mask = (sub_mask - 1) & mask
            ans[i] = total
        return ans


if __name__ == "__main__":
    obj = Solution()
    print(
        obj.findNumOfValidWords(
            words=["aaaa", "asas", "able", "ability", "actt", "actor", "access"],
            puzzles=["aboveyz", "abrodyz", "abslute", "absoryz", "actresz", "gaswxyz"],
        )
    )
    print(
        obj.findNumOfValidWords(
            words=["apple", "pleas", "please"],
            puzzles=["aelwxyz", "aelpxyz", "aelpsxy", "saelpxy", "xaelpsy"],
        )
    )