1178.md

1178. Number of Valid Words for Each Puzzle

Solution 1 (time O(m+n), space O(m))

class Solution(object):
    def findNumOfValidWords(self, words, puzzles):
        """
        :type words: List[str]
        :type puzzles: List[str]
        :rtype: List[int]
        """
        freq = collections.Counter()
        for word in words:
            mask = 0
            for ch in word:
                mask |= (1 << (ord(ch) - ord('a')))
            freq[mask] += 1
        ans = []
        for puzzle in puzzles:
            total = 0
            for perm in self.subset(puzzle[1:]):
                mask = 1 << (ord(puzzle[0]) - ord('a'))
                for ch in perm:
                    mask |= (1 << (ord(ch) - ord('a')))
                if mask in freq:
                    total += freq[mask]
            ans.append(total)
        return ans

    def subset(self, word):
        ans = [""]
        for c in word:
            ans.extend([c + cur_ans for cur_ans in ans])
        return ans