Problem statement

https://leetcode.com/problems/number-of-valid-words-for-each-puzzle/

Solution

The idea is to create bitmask for each word and create counter of all words. Then we iterate over puzzles and for each puzzle we need to get 2^6 (not 2^7, becauswe first symbol should be used) possible submasks and check how many times each of them used, using our counter. Here I use trick how to traverse all submasks, it can be done in different way, for example with bfs.

Complexity

Time complexity is O(M + P*2^6), where M is total length of words and P is number of puzzles we have.

Code

class Solution:
    def findNumOfValidWords(self, words, puzzles):
        def get_mask(s):
            return reduce(lambda x, y: x|y, [1<<(ord(c) - 97) for c in s])
        
        ans, cnt = [0]*len(puzzles), Counter()
        for word in words: cnt[get_mask(word)] += 1

        for i, puzzle in enumerate(puzzles):
            mask = get_mask(puzzle[1:])
            addon = 1<<(ord(puzzle[0]) - 97)
            submask = mask
            while submask:
                ans[i] += cnt[submask|addon]
                submask = (submask - 1) & mask
            ans[i] += cnt[addon]
            
        return ans