Number of Valid Words for Each Puzzle — LeetCode 1178 Python Solution

The problem

With respect to a given puzzle string, a word is valid if both the following conditions are satisfied: word contains the first letter of puzzle. For each letter in word, that letter is in puzzle.

Example

Input

words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"]

Output

[1,1,3,2,4,0]

Explanation

1 valid word for "aboveyz" : "aaaa"

Python solution

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = Counter()
        for w in words:
            mask = 0
            for c in w:
                mask |= 1 << (ord(c) - ord("a"))
            cnt[mask] += 1

        ans = []
        for p in puzzles:
            mask = 0
            for c in p:
                mask |= 1 << (ord(c) - ord("a"))
            x, i, j = 0, ord(p[0]) - ord("a"), mask
            while j:
                if j >> i & 1:
                    x += cnt[j]
                j = (j - 1) & mask
            ans.append(x)
        return ans

Complexity

Pattern: Trie

Store a set of words by their shared prefixes so lookups cost the length of the word. LeetCode 1178. Number of Valid Words for Each Puzzle is filed here because LeetCode tags it Trie, which is the vocabulary this hub collects.

The trie guide has the Python template for the pattern and the 49 LeetCode problems that use it.

Related problems