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.
        For example, if the puzzle is "abcdefg", then valid words are "faced", "cabbage", and "baggage"; while invalid words are "beefed" (doesn't include "a") and "based" (includes "s" which isn't in the puzzle).

Return an array answer, where answer[i] is the number of words in the given word list words that are valid with respect to the puzzle puzzles[i].
 
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" 
1 valid word for "abrodyz" : "aaaa"
3 valid words for "abslute" : "aaaa", "asas", "able"
2 valid words for "absoryz" : "aaaa", "asas"
4 valid words for "actresz" : "aaaa", "asas", "actt", "access"
There're no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.

 
Constraints:

1 <= words.length <= 10^5
4 <= words[i].length <= 50
1 <= puzzles.length <= 10^4
puzzles[i].length == 7
words[i][j], puzzles[i][j] are English lowercase letters.
Each puzzles[i] doesn't contain repeated characters.

Difficulty: interview

Starter code:

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        

Solutions:
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # 1st step
        # construct a mask for each word
        # note that there may be duplicate mask for different words
        # so we need a dict to count the number
        orda = ord('a') # 97
        mask = defaultdict(int) # word mask
        
        for w in words:
            m = 0
            for c in w:
                m |= 1 << (ord(c) - orda)
            mask[m] += 1
        
        # 2nd step
        # for each puzzle, construct the corresponding mask for each possible valid word, check whether the word is in mask
        res = []
        for p in puzzles:
            ones = []
            # separate current puzzle into ones, 'bdeg' -> 0b1011010 -> [0b10(b), 0b1000(d), 0b10000(e), 0b1000000(g)]
            for c in p:
                ones.append(1 << (ord(c) - orda))
            
            # generate all valid words for the current puzzle
            # equivalent to generate all subsets of ones[1:]
            # reuse code from [78. Subsets]
            valid = [ones[0]] # valid word must contains the first char of current puzzle
            for i in range(1,7): # bfs to generate all valid words
                valid.extend([ones[i] + v for v in valid])
            
            # for each valid word, check whether it's in mask
            novw = 0 # number of valid words for current puzzle
            for v in valid:
                if v in mask:
                    novw += mask[v]
            res.append(novw)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        res = []
        
        counter = collections.defaultdict(int)
        
        for word in words:
            mask = 0
            for c in word:
                mask |= 1 << (ord(c) - ord('a'))
            
            counter[mask] += 1
        
        for puzzle in puzzles:
            mask = 0
            for c in puzzle:
                mask |= 1 << (ord(c) - ord('a'))
            
            first = 1 << (ord(puzzle[0]) - ord('a'))
            
            c = 0
            sub = mask
            
            while True:
                if sub & first == first and sub in counter:
                    c += counter[sub]
                
                if sub == 0:
                    break
                    
                sub = (sub-1)&mask
            
            res.append(c)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        word_profiles = {}
        letters = \"abcdefghijklmnopqrstuvwxyz\"
        for word in words:
            word_profile = 0
            for letter in word:
                word_profile |= 1<<letters.index(letter)
            if not word_profile in word_profiles:
                word_profiles[word_profile] = 0
            word_profiles[word_profile] += 1
        
        for puzzle in puzzles:
            puzzle_profile = 0
            for letter in puzzle:
                puzzle_profile |= 1<<letters.index(letter)
            
            first_letter = 1<<letters.index(puzzle[0])
            
            candidate = puzzle_profile
            cnt = 0
            while candidate > 0:
                if candidate in word_profiles and candidate&first_letter == first_letter:
                    cnt += word_profiles[candidate]
                candidate -= 1
                candidate &= puzzle_profile
            
            yield(cnt)

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        ## TLE
        #bitWords = []
        #for word in words:
        #    n = 0  
        #    for w in word:
        #        n = n | 1 << (ord(w) - ord('a'))
        #    bitWords.append(n)
        #        
        #result = []
        #for puzzle in puzzles:
        #    n = 0  
        #    f = 0
        #    for p in puzzle:
        #        n = n | 1 << (ord(p) - ord('a'))
        #    f = 1 << (ord(puzzle[0]) - ord('a'))
        #    cnt = 0
        #    for i in range(len(bitWords)):
        #        w = bitWords[i]
        #        if f & w and not (n & w)^w:
        #            cnt += 1 
        #    result.append(cnt) 
        #return result 
        
        # TLE
        # 중복이 많이 개선됨
        count = collections.Counter()
        for word in words:
            n = 0  
            for w in word:
                n = n | 1 << (ord(w) - ord('a'))
            count[n] += 1
                
        result = []
        for puzzle in puzzles:
            bfs = [1 << (ord(puzzle[0]) - 97)]
            m = 0
            # 모든 조합 찾기
            for p in puzzle[1:]:
                bfs += [m | 1 << (ord(p) - 97) for m in bfs]
                
            # 결과
            result.append(sum(count[m] for m in bfs))
        return result 
    
        ## 604
        #count = collections.Counter()
        #for w in words:
        #    if len(set(w)) > 7: continue
        #    m = 0
        #    for c in w:
        #        m |= 1 << (ord(c) - 97)
        #    count[m] += 1
        #    
        #res = []
        #for p in puzzles:
        #    bfs = [1 << (ord(p[0]) - 97)]
        #    for c in p[1:]:
        #        bfs += [m | 1 << (ord(c) - 97) for m in bfs]
        #        print(bfs)
        #    res.append(sum(count[m] for m in bfs))
        #return res


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter()
        
        for word in words:
            m = 0
            for c in word:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
            
        res = []
        for puzzle in puzzles:
            bfs = [1 << (ord(puzzle[0]) - 97)]
            
            for c in puzzle[1:]:
                bfs += [x | (1 << (ord(c)-97) )for x in bfs]
                
            res.append(sum(count[x] for x in bfs))
            
        return res

from collections import defaultdict

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        ans = [0] * len(puzzles)
        wordSet = {}
        for i, word in enumerate(words):
            mask = 0
            for char in word:
                mask |= 1 << (ord(char) - ord('a'))
            wordSet[mask] = wordSet.get(mask, 0)+1
                    
        for i in range(len(puzzles)):
            first = 1 << (ord(puzzles[i][0]) - ord('a'))
            bitSet = 0
            for char in puzzles[i]:
                bitSet |= 1 << (ord(char) - ord('a'))
            mask = bitSet
            while True:
                if first & mask == first:
                    ans[i] += wordSet.get(mask, 0)
                if mask == 0:
                    break
                
                mask = (mask-1) & bitSet
        return ans

class Solution:
\t# Generates a bit mask given a word, where the i-th bit being 1 mean
\t# the word contains the i-th letter of the alphabet.
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask
    
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if (subMask >> firstBitIndex) & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution
                
        

class Solution:
    # [1]
\t# Generates a bit mask given a word, where the i-th bit being 1 mean
\t# the word contains the i-th letter of the alphabet.
\t# For example the word 'acf' -> 100101 because a, c, f are the 1st, 3rd,
\t# and 6th letters of the alphabet, so those corresponding bits are 1.
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if subMask >> firstBitIndex & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:        
        
        count=collections.Counter()
        for w in words:
            if len(set(w))>7:
                continue
            
            m=0
            
            for c in w:
                m|=(1<<(ord(c)-ord('a')))
            
            count[m]+=1
        
        res=[]
        
        for p in puzzles:
            bfs=[1<<(ord(p[0])-ord('a'))]
            
            for c in p[1:]:
                bfs+=[m|1<<(ord(c)-ord('a')) for m in bfs ]
            
            m=0
            for i in bfs:
                m+=count[i]
            
            res.append(m)
        
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        wdict=defaultdict(int)
        def getbitmask(word):
            mask=0
            for w in word:
                i=ord(w)-ord('a')
                mask |= 1 << i
            return mask
        
        op=[0]*len(puzzles)
        for word in words:
            mask=getbitmask(word)
            wdict[mask]+=1
        
        for i,pz in enumerate(puzzles):
            mask=getbitmask(pz)
            fi=ord(pz[0])-ord('a')
            submask=mask
            count=0
            while submask!=0:
                if submask>>fi&1:
                    count+=wdict[submask]
                submask=(submask-1)&mask
            op[i]=count
            
        return op
            


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        wdict=defaultdict(int)
        def getbitmask(word):
            mask=0
            for w in word:
                i=ord(w)-ord('a')
                mask |= 1 << i
            return mask
        
        op=[0]*len(puzzles)
        for word in words:
            mask=getbitmask(word)
            wdict[mask]+=1
        
        for i,pz in enumerate(puzzles):
            mask=getbitmask(pz)
            fi=ord(pz[0])-ord('a')
            submask=mask
            count=0
            while True:
                if submask>>fi&1:
                    count+=wdict[submask]
                if submask==0:
                    break
                submask=(submask-1)&mask
            op[i]=count
            
        return op
            


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        
        count = collections.defaultdict(int)
        for i, w in enumerate(words):
            mask = 0
            for x in w:
                mask |= 1 << (ord(x) - ord('a'))
            count[mask] += 1
            
        for i, p in enumerate(puzzles):
            mask = 0
            for x in p:
                mask |= 1 << (ord(x) - ord('a'))
            
            first = 1 << ord(puzzles[i][0]) - ord('a')
            
            c = 0
            sub = mask
            while True:
                if sub & first == first and sub in count:
                    c += count[sub]
                
                if sub == 0:
                    break
                
                sub = (sub-1)&mask
            res.append(c)
        
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter()
        for w in words:
            if len(set(w)) > 7: continue
            m = 0
            for c in w:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
        res = []
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - 97)]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - 97) for m in bfs]
            res.append(sum(count[m] for m in bfs))
        return res


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            subs = [p[0]]
            for c in p[1:]:
                subs += [s + c for s in subs]
            res.append(sum(count[frozenset(s)] for s in subs))
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        wordMap = {}
        for word in words:
            encode = 0
            for char in word:
                encode |= 1<<(ord(char)-ord(\"a\"))
            wordMap[encode] = wordMap.get(encode, 0)+1
            
        
        wordCount = []
        for puzzle in puzzles:
            mask = 0
            for char in puzzle:
                mask |= 1<<(ord(char)-ord(\"a\"))
                
            substring = mask

            first = 1<<ord(puzzle[0])-ord(\"a\")
            count = 0
            while substring:
                if (first&substring)==first and substring in wordMap:
                    count += wordMap[substring]
                    
                substring = (substring-1)&mask
                
            wordCount.append(count)
            
        return wordCount
                    
                
                
            
            
                                

class Solution(object):
    def findNumOfValidWords(self, words, puzzles):
        def get_bit(word):
            x=0
            for ch in (word):
                x|=1<<(ord(ch)-ord('a'))
            return x
        bitdic=collections.defaultdict(int)
        words=[set(list(x)) for x in words]
        for word in words:
            bitdic[get_bit(word)]+=1
        res=[]
        for puzzle in puzzles:
            count=0
            first=puzzle[0]
            bfs=[1<<(ord(first)-ord('a'))]
            for ch in set(puzzle[1:]):
                bfs+=[x|1<<(ord(ch)-ord('a')) for x in bfs]
            res.append(sum(bitdic[x] for x in set(bfs)))
        return res


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            subs = [p[0]]
            for c in p[1:]:
                subs += [s + c for s in subs]
            res.append(sum(count[frozenset(s)] for s in subs))
        return res


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        ans = []
        count = collections.Counter(frozenset(w) for w in words)
        for p in puzzles:
            subs = [p[0]]
            for c in p[1:]:
                subs += [s + c for s in subs]
            ans.append(sum(count[frozenset(s)] for s in subs))
        return ans

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        cnt = collections.Counter(''.join(sorted(set(w))) for w in words)
        for p in puzzles:
            bfs = [p[0]]
            for c in p[1:]:
                bfs += [s + c for s in bfs]
            res.append(sum(cnt[''.join(sorted(s))] for s in bfs))
        return res  
        
#         wordCounter = defaultdict(int)
#         chars = \"abcdefghijklmnopqrstuvwxyz\"
#         shiftDict = {chars[i]: (1<<(ord(chars[i]) - 97)) for i in range(26)}
#         wordCounter1 = Counter(\"\".join(sorted(set(word))) for word in words)
        
#         for word in wordCounter1:
#             mask = 0
#             for char in word:
#                 mask |= shiftDict[char]
#             wordCounter[mask] += wordCounter1[word]
        
#         ans = []
#         maxMask = (1<<26)-1
#         dp = {}
#         for puzzle in puzzles:
#             pMask = 0
#             for char in set(puzzle):
#                 pMask |= shiftDict[char]
#             pMask ^= maxMask
#             subAns = 0
#             if (pMask, puzzle[0]) in dp:
#                 ans.append(dp[(pMask, puzzle[0])])
#             else:
#                 for wMask in wordCounter:
#                     if wMask & shiftDict[char] and (wMask & pMask == 0):
#                         subAns += wordCounter[wMask]
#                 dp[(pMask, puzzle[0])] = subAns
#                 ans.append(subAns)
#         return ans
        
        # charSetDict = defaultdict(set)
        # wordSubSetDict = {}
        # for word in words:
        #     wordSubSetDict[word] = set(word)
        #     for char in word:
        #         charSetDict[char].add(word)
        # ans = []
        # for puzzle in puzzles:
        #     subAns = 0
        #     pCharSet = set(puzzle)
        #     for word in charSetDict[puzzle[0]]:
        #         if wordSubSetDict[word].issubset(pCharSet):
        #             subAns += 1
        #     ans.append(subAns)
        # return ans


import numpy

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        cnt = collections.Counter(''.join(sorted(set(w))) for w in words)
        for p in puzzles:
            bfs = [p[0]]
            for c in p[1:]:
                bfs += [s + c for s in bfs]
            res.append(sum(cnt[''.join(sorted(s))] for s in bfs))
        return res

class Solution:
    wdMap = {}
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        self.wdMap = self.hashwords(words)
        for puzzle in puzzles:
            res.append(self.checkValidWord(puzzle, 0, 0))

        return res

    def checkValidWord(self, puzzle, i, id):
        if i == len(puzzle):
            return self.wdMap.get(id , 0)
        indx = ord(puzzle[i]) - ord('a')
        nextid = id | (1<<indx)
        if i == 0:
            return self.checkValidWord(puzzle, i + 1, nextid)
        else:
            return self.checkValidWord(puzzle, i + 1, id) + self.checkValidWord(puzzle, i+1, nextid)


    def hashwords(self, words):
        wdMap = {}
        for word in words:
            letter_id = 0
            for letter in word:
                indx = ord(letter) - ord('a')
                letter_id = letter_id | (1 << indx)
            wdMap[letter_id] = wdMap.get(letter_id, 0) + 1
        return wdMap


class Solution:
    
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # 97 = ord('a')
        
        def wordToInt(word: str) -> int:
            n  = 0
            ls = 0
            for c in word:
                cn = 1 << (ord(c) - 97)
                ls += 1 if cn & n == 0 else 0
                if ls > 7:
                    return None
                n |= cn
            return n
        
        def validWords(ws, puzzle: str) -> int:
            return sum( (ws[n] if n in ws else 0) for n in getPossibleNums(puzzle, 0) ) 
        
        def getPossibleNums(puzzle: str, i: int) -> List[int]:
            cn = 1 << (ord(puzzle[i]) - 97)
            if i == len(puzzle) - 1:
                return [cn, 0]
            elif i == 0:
                return [ n | cn for n in getPossibleNums(puzzle, 1) ]
            else:
                tmp = getPossibleNums(puzzle, i+1)
                return [ n | cn for n in tmp ] + tmp
        
        ws = {}
        for w in words:
            n = wordToInt(w)
            if n is not None:
                ws[n] = 1 + (ws[n] if n in ws else 0)
            
        return list(map(lambda p: validWords(ws, p), puzzles))

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        words = [frozenset(word) for word in words if len(set(word)) <= 7]
        counter = Counter(words)
        res = []
        for p in puzzles:
            pre = (p[0],)
            t = set(p[1:])
            tmp = 0
            for i in range(len(t) + 1):
                for c in itertools.combinations(t, i):
                    tmp += counter[frozenset(pre + c)]
            res += [tmp]
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for c in itertools.combinations(p[1:], k):
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

    def findNumOfValidWords2(self, words, puzzles):
        count = collections.Counter()
        for w in words:
            if len(set(w)) > 7: continue
            m = 0
            for c in w:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
        res = []
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - 97)]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - 97) for m in bfs]
            res.append(sum(count[m] for m in bfs))
        return res
    
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask

    def findNumOfValidWords1(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if subMask >> firstBitIndex & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution

from collections import defaultdict

class Solution:
    def getBitRepr(word):
        \"\"\"
        >>> Solution.getBitRepr('abc')
        7
        \"\"\"
        result = 0
        for char in word:
            result |= (1 << (ord(char) - ord('a')))
        return result

    def countCanonicalWords(words):
        \"\"\"
        >>> Solution.countCanonicalWords(['abc', 'bca'])
        {7: 2}
        \"\"\"
        countMap = defaultdict(int)
        for word in words:
            bitMask = Solution.getBitRepr(word)
            countMap[bitMask] += 1
        return countMap

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        canonicalWordCount = Solution.countCanonicalWords(words)
        puzzlesMasks = [Solution.getBitRepr(x) for x in puzzles]
        result = []

        for i, puzzleBitMask in enumerate(puzzlesMasks):
            matchCount = 0
            candidateWordMask = puzzleBitMask
            firstCharMask = Solution.getBitRepr(puzzles[i][0])
            while candidateWordMask != 0:
                if (candidateWordMask & firstCharMask != 0):
                   matchCount += canonicalWordCount[candidateWordMask]
                candidateWordMask = (candidateWordMask - 1) & puzzleBitMask
            result.append(matchCount)
        return result

class Solution:
    def findNumOfValidWords(self, words, puzzles):
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for c in itertools.combinations(p[1:], k):
                    # print(c)
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        #the output list
        res = [0] * len(puzzles)
        
        #set up the trie using dictionary
        dic = {}
        for word in words:
            cur = dic
            for letter in sorted(set(word)):
                if letter not in cur:
                    cur[letter] = {}
                cur = cur[letter]
            # if only this word contains all the letters along the branch
            if '*' not in cur:
                cur['*'] = 1
                
            # if there exists other words that contain all the 
            # letters along the branch
            else:
                cur['*'] += 1
        
        # search the trie using depth first search;
        # check_head checks whether the first letter of puzzle is in the word
        def dfs(dic, i, check_head):
            p = puzzles[i]
            if '*' in dic and check_head:
                # add the number of words that meet the specification to the                        
\t\t\t\t# corresponding position of puzzle
                res[i] += dic['*']
            for key in dic:
                if key in p:
                    if p[0] == key or check_head:
                        dfs(dic[key], i, True)
                    else:
                        dfs(dic[key], i, False)
            else:
                return
        
        # run dfs for all puzzles
        for i in range(len(puzzles)):
            dfs(dic, i, False)
        
        
        # return result
        return res 

class Solution:
    def conv(self, c):
        return ord(c) - ord('a')
    
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        first_letters = {chr(c): set([]) for c in range(ord('a'), ord('z') + 1)} # maps chars to set of words containing the char
        word_masks = {} # maps bitmask of word to its index
        for i, w in enumerate(words):
            mask = 0
            for c in w:
                first_letters[c].add(i)
                mask = (1 << self.conv(c)) | mask
            if mask not in word_masks:
                word_masks[mask] = []
            word_masks[mask].append(i)
        puzzle_masks = []
        for p in puzzles:
            mask = 0
            for c in p:
                mask = (1 << self.conv(c)) | mask
            puzzle_masks.append(mask)
        
        answer = []
        for i, m in enumerate(puzzle_masks):
            s = m
            total = 0
            while s != 0:
                if s in word_masks:
                    for w in word_masks[s]:
                        if w in first_letters[puzzles[i][0]]:
                            total += 1
                s = (s - 1) & m
            answer.append(total)
        
        return answer

import collections
import itertools
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        answer = [0] * len(puzzles)
        count = collections.Counter([frozenset(word) for word in words if len(set(word)) <= 7])
        
        for i, p in enumerate(puzzles):
            answer[i] = sum([count[frozenset(p[0] + \"\".join(s))]  for j in range(0, len(p)) for s in itertools.combinations(p[1:], j)])
            
        return answer

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        wordPatternCnt = collections.defaultdict(int)
        
        for word in words:
            pattern = 0
            for letter in word:
                pattern |= (1 << ord(letter) - ord(\"a\"))
            wordPatternCnt[pattern] += 1
        
        res = []
        
        for puzzle in puzzles:
            cnt = 0
            pattern = 0
            for letter in puzzle:
                pattern |= (1 << (ord(letter) - ord(\"a\")))
                
            subPattern = pattern
                
            while subPattern > 0:
                if subPattern & (1 << (ord(puzzle[0]) - ord(\"a\"))):
                    cnt += wordPatternCnt[subPattern]
                subPattern = pattern & (subPattern - 1)
            
            res.append(cnt)
        
        return res
                

import collections
import itertools
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        answer = [0] * len(puzzles)
        count = collections.Counter([frozenset(word) for word in words if len(set(word)) <= 7])
        
        for i, p in enumerate(puzzles):
            answer[i] = sum([count[frozenset(p[0] + \"\".join(s))]  for j in range(len(p)) for s in itertools.combinations(p[1:], j)])
            
        return answer

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def getNum(s: str) -> int:
            res = 0
            for c in s:
                res |= (1 << (ord(c) - 97))
            return res
        
        counter = Counter([getNum(set(word)) for word in words if len(set(word)) < 8])
        ans = []
        dic = dict()
        for puzzle in puzzles:
            sub = [(1 << (ord(puzzle[0]) - 97))]
            for c in puzzle[1:]:
                sub += [m | (1 << (ord(c) - 97)) for m in sub]
            ans.append(sum(counter[w] for w in sub))
            
        return ans


from collections import Counter, deque


def make_bitmask(s):
    val = 0x0000
    for si in s:
        val |= (1 << ord(si) - ord('a'))
    return val


def is_submask(maskA, maskB):
    return maskA == (maskA & maskB)


def debug(n):
    s = \"\"
    for i in range(26):
        if (1 << i) & n:
            s += chr(i + ord('a'))
    return s


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        counts = Counter(map(make_bitmask, words))
        
        ret = [0 for _ in range(len(puzzles))]
        for i, p in enumerate(puzzles):
            queue = deque([(make_bitmask(p[0]), 1)])
            val = 0
            seen = set()
            while queue:
                n, depth = queue.popleft()
                if n not in seen:
                    val += counts[n]
                    seen.add(n)
                while depth < len(p):
                    queue.append((n | make_bitmask(p[depth]), depth + 1))
                    depth += 1
            ret[i] = val
        return ret

from itertools import combinations
from collections import defaultdict
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
            wordmap = defaultdict(int)
            for word in words:
                mask = 0
                for c in word:
                    mask = mask | (1<<(ord(c)-ord('a')))
                wordmap[mask] += 1
            ans = [0 for i in range(len(puzzles))]
            for i, p in enumerate(puzzles):
                starting_letter = p[0]
                for k in range(0, len(p[1:])+1):
                    for comb in combinations(p[1:], k):
                        mask = 1<<(ord(starting_letter)-  ord('a'))
                        for c in comb:
                            mask = mask | (1<<(ord(c)-ord('a')))
                        ans[i] += wordmap[mask]
            return ans

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        counter = {}
        for word in words:
            mask = self.to_int(word)
            if mask not in counter:
                counter[mask] = 0
            counter[mask] += 1
                
        output = []
        for puzzle in puzzles:
            output.append(0)
            sub_strings = ['']
            mask = self.to_int(puzzle[1:])
            for c in puzzle[1:]:
                for sub_string in list(sub_strings):
                    sub_strings.append(sub_string+c)
            for sub_string in list(sub_strings):
                mask = self.to_int(puzzle[0] + sub_string)
                output[-1] += counter.get(mask, 0)
            
        return output
    
    def to_int(self, word):
        mask = 0
        for ch in word:
            mask |= 1 << (ord(ch) - 97)
        return mask


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        #the output list
        res = [0] * len(puzzles)
        
        #set up the trie using dictionary
        dic = {}
        for word in words:
            cur = dic
            for letter in sorted(set(word)):
                if letter not in cur:
                    cur[letter] = {}
                cur = cur[letter]
            # if only this word contains all the letters along the branch
            if '*' not in cur:
                cur['*'] = 1
                
            # if there exists other words that contain all the 
            # letters along the branch
            else:
                cur['*'] += 1
        
        # search the trie using depth first search;
        # check_head checks whether the first letter of puzzle is in the word
        def dfs(dic, i, check_head):
            p = puzzles[i]
            if '*' in dic and check_head:
                # add the number of words that meet the specification to the                        
\t\t\t\t# corresponding position of puzzle
                res[i] += dic['*']
            for key in dic:
                if key in p:
                    if p[0] == key or check_head:
                        dfs(dic[key], i, True)
                    else:
                        dfs(dic[key], i, False)
            else:
                return
        
        # run dfs for all puzzles
        for i in range(len(puzzles)):
            dfs(dic, i, False)
        
        
        # return result
        return res     

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = {}
        result = [0 for _ in range(len(puzzles))]
        
        def dfs(puzzle, i, trie, hasFirst=False):        
            if \"*\" in trie and hasFirst:
                result[i] += trie[\"*\"]
                        
            for c in puzzle:
                if c in trie:
                    dfs(puzzle, i, trie[c], hasFirst or c == puzzle[0])
                            
        for w in words:
            curr = trie
            for c in sorted(set(w)):
                curr = curr.setdefault(c, {})
                    
                # curr = curr[c]
            
            if \"*\" in curr:
                curr[\"*\"] += 1
            else:
                curr[\"*\"] = 1
            
        print(curr)
            
        for i, p in enumerate(puzzles):
            dfs(p, i, trie)
            
        return result


# 1178. Number of Valid Words for Each Puzzle
# version 2. backwards.

def gist (word):
    ans = 0
    for ch in word:
        ans |= (1 << (ord (ch) - ord ('a')))
    return ans

def subsets (arr, start=0, progress=0):
    if start == len (arr):
        yield progress
    else:
        yield from subsets (arr, start+1, progress | arr[start])
        yield from subsets (arr, start+1, progress)

def head_subsets (puzzle):
    bits = [gist (ch) for ch in puzzle]
    for mask in subsets (bits[1:]):
        yield mask | bits[0]

def count_solutions (words, puzzles):
    gist_count = {}
    for word in words:
        g = gist (word)
        gist_count.setdefault (g, 0)
        gist_count[g] += 1

    ans = []
    for puzzle in puzzles:
        count = sum (gist_count.get (g, 0) for g in head_subsets (puzzle))
        ans.append (count)

    return ans

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        return count_solutions(words, puzzles)

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cc = collections.Counter()
        for w in words:
            cc[tuple(sorted(set(list(w))))] += 1
        
        res = []
        for pzl in puzzles:
            possible_sets = [set([pzl[0]])]
            for i in range(1, 7):
                possible_sets.extend([st.union([pzl[i]]) for st in possible_sets])
            nvalid = sum(cc[tuple(sorted(st))] for st in possible_sets)
            res.append(nvalid)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        res = []
        cnt = collections.Counter(''.join(sorted(set(w))) for w in words)
        for p in puzzles:
            bfs = [p[0]]
            for c in p[1:]:
                bfs += [s + c for s in bfs]
            res.append(sum(cnt[''.join(sorted(s))] for s in bfs))
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = {}
        # trie = defaultdict(dict)
    
        result = [0 for _ in range(len(puzzles))]
                    
        def dfs(puzzle, i, trie, hasFirst=False):        
            if \"*\" in trie and hasFirst:
                result[i] += trie[\"*\"]
                        
            val = 0
                    
            for c in puzzle:
                if c in trie:
                    dfs(puzzle, i, trie[c], hasFirst or c == puzzle[0])
                            
        for w in words:
            curr = trie
            for c in sorted(set(w)):
                curr = curr.setdefault(c, {})
                
                # curr = curr.setdefault(c, defaultdict(int))
              
            if \"*\" not in curr:
                curr[\"*\"] = 0
            curr[\"*\"] += 1
            
            # if \"*\" in curr:
            #     curr[\"*\"] += 1
            # else:
            #     curr[\"*\"] = 1
            
        for i, p in enumerate(puzzles):
            dfs(p, i, trie)
            
        return result

class Solution:
    # [1]
\t# Generates a bit mask given a word, where the i-th bit being 1 mean
\t# the word contains the i-th letter of the alphabet.
\t# For example the word 'acf' -> 100101 because a, c, f are the 1st, 3rd,
\t# and 6th letters of the alphabet, so those corresponding bits are 1.
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if subMask >> firstBitIndex & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = {}
        result = [0 for _ in range(len(puzzles))]
        
        def dfs(puzzle, i, trie, hasFirst=False):        
            if \"*\" in trie and hasFirst:
                result[i] += trie[\"*\"]
                        
            for c in puzzle:
                if c in trie:
                    dfs(puzzle, i, trie[c], hasFirst or c == puzzle[0])
                            
        for w in words:
            curr = trie
            for c in sorted(set(w)):
                curr = curr.setdefault(c, {})
                    
                # curr = curr[c]
            
            if \"*\" in curr:
                curr[\"*\"] += 1
            else:
                curr[\"*\"] = 1
            
        print(curr)
            
        for i, p in enumerate(puzzles):
            dfs(p, i, trie)
            
        return result

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = {}
        # trie = defaultdict(dict)
    
        result = [0 for _ in range(len(puzzles))]
                    
        def dfs(puzzle, i, trie, hasFirst=False):        
            if \"*\" in trie and hasFirst:
                result[i] += trie[\"*\"]
                        
            val = 0
                    
            for c in puzzle:
                if c in trie:
                    dfs(puzzle, i, trie[c], hasFirst or c == puzzle[0])
                            
        for w in words:
            curr = trie
            for c in sorted(set(w)):
                curr = curr.setdefault(c, {})
                
                # curr = curr.setdefault(c, defaultdict(int))
              
            # if \"*\" not in curr:
            #     curr[\"*\"] = 0
            # curr[\"*\"] += 1
            
            if \"*\" in curr:
                curr[\"*\"] += 1
            else:
                curr[\"*\"] = 1
            
        for i, p in enumerate(puzzles):
            dfs(p, i, trie)
            
        return result

class Solution:
    def findNumOfValidWords(self, words, puzzles):
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for c in itertools.combinations(p[1:], k):
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            subs = [p[0]]
            for c in p[1:]:
                subs += [s + c for s in subs]
            res.append(sum(count[frozenset(s)] for s in subs))
        return res

from collections import defaultdict

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        tri = defaultdict(lambda: 0)
        for word in words:
            cur = tri
            letters = sorted(set(word))
            for i in range(len(letters)):
                if letters[i] in cur:
                    cur = cur[letters[i]]
                else:
                    cur[letters[i]] = defaultdict(lambda: 0)
                    cur = cur[letters[i]]
                if i == len(letters) - 1:
                    if '*' in cur:
                        cur['*'] += 1
                    else:
                        cur['*'] = 1
                    
        returnArr = [0] * len(puzzles)
        
        def helper(tri, puzzle, i,  found_first):
            firstLetter = puzzle[0]
            if '*' in tri and found_first:
                returnArr[i] += tri['*']
            for letter in tri:
                if letter in puzzle:
                    if firstLetter  == letter or found_first:
                        helper(tri[letter], puzzle, i, True)
                    else:
                        helper(tri[letter], puzzle, i, False)
            
        
        for i in range(len(puzzles)):
            helper(tri, puzzles[i], i, False)
            
        return returnArr

class Solution:
    def findNumOfValidWords1(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for c in itertools.combinations(p[1:], k):
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

    def findNumOfValidWords2(self, words, puzzles):
        count = collections.Counter()
        for w in words:
            if len(set(w)) > 7: continue
            m = 0
            for c in w:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
        res = []
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - 97)]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - 97) for m in bfs]
            res.append(sum(count[m] for m in bfs))
        return res
    
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask

    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if subMask >> firstBitIndex & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution

import collections
class Node(object):
    def __init__(self):
        self.dic = collections.defaultdict(Node)
        self.counter = 0
        
    def insert(self, word):
        if not word:
            return
        node = self.dic[word[0]]
        for ind in range(1, len(word)):
            node = node.dic[word[ind]]
        node.counter += 1
        
            
class Solution(object):
    def findNumOfValidWords(self, words, puzzles):
        \"\"\"
        :type words: List[str]
        :type puzzles: List[str]
        :rtype: List[int]
        \"\"\"
        
        def dfs(puzzle, i, node):
            if i == len(puzzle):
                self.count += node.counter
                return 
            
            if puzzle[i] == self.initial:
                if puzzle[i] not in node.dic:
                    return
                dfs(puzzle, i + 1, node.dic[puzzle[i]])
                
            else:
                dfs(puzzle, i + 1, node)
                if puzzle[i] not in node.dic:
                    return
                dfs(puzzle, i + 1, node.dic[puzzle[i]])
        
        trie = Node()
        for word in words:
            word = ''.join(sorted(set(word)))
            trie.insert(word)
        
        
        final = [0 for _ in range(len(puzzles))]
        for ind in range(len(puzzles)):
            self.initial = puzzles[ind][0]
            self.count = 0
            puzzle = ''.join(sorted(set(puzzles[ind])))
            dfs(puzzle, 0, trie)
            final[ind] = self.count
            
        return final

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # cnt = Counter(frozenset(w) for w in words if len(set(w)) <= 7)
        # ans = []
        # for p in puzzles:
        #     cur = 0
        #     for k in range(7):
        #         for i in itertools.combinations(p[1:], k):
        #             cur += cnt[frozenset((p[0],) + i)]
        #     ans.append(cur)
        # return ans
                    
        
        
        ans = []
        cnt = Counter()
        for w in words:
            w = set(w)
            if len(w) > 7:
                continue
            w_bit = 0
            for c in w:
                w_bit |= 1 << ord(c) - ord('a')
            cnt[w_bit] += 1
        for p in puzzles:
            bfs = [1 << ord(p[0]) - ord('a')]
            for c in p[1:]:
                bfs += [m | 1 << ord(c) - ord('a') for m in bfs]
            ans.append(sum(cnt[m] for m in bfs))
        return ans


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        ans = []
        cnt = Counter()
        for w in words:
            w = set(w)
            if len(w) > 7:
                continue
            w_bit = 0
            for c in w:
                w_bit |= 1 << ord(c) - ord('a')
            cnt[w_bit] += 1
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - ord('a'))]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - ord('a')) for m in bfs]
            ans.append(sum(cnt[m] for m in bfs))
        return ans
        #     cur = 0
        #     p_bit = 0
        #     for c in p:
        #         p_bit |= 1 << ord(c) - ord('a')
        #     a = 1 << ord(p[0]) - ord('a')
        #     for w in cnt:
        #         if a & w and w & p_bit == w:
        #             cur += cnt[w]
        #     ans.append(cur)
        # return ans


class Solution:
    
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        # 97 = ord('a')
        
        def wordToInt(word: str) -> int:
            n  = 0
            ls = 0
            for c in word:
                cn = 1 << (ord(c) - 97)
                ls += 1 if cn & n == 0 else 0
                if ls > 7:
                    return None
                n |= cn
            return n
        
        def validWords(ws, puzzle: str) -> int:
            return sum( (ws[n] if n in ws else 0) for n in getPossibleNums(puzzle, 0) ) 
        
        def getPossibleNums(puzzle: str, i: int) -> List[int]:
            cn = 1 << (ord(puzzle[i]) - 97)
            if i == len(puzzle) - 1:
                return [cn, 0]
            elif i == 0:
                return [ n | cn for n in getPossibleNums(puzzle, 1) ]
            else:
                tmp = getPossibleNums(puzzle, i+1)
                return [ n | cn for n in tmp ] + tmp
        
        ws = {}
        for w in words:
            n = wordToInt(w)
            if n is not None:
                ws[n] = 1 + (ws[n] if n in ws else 0)
            
        return map(lambda p: validWords(ws, p), puzzles)

import string
from collections import defaultdict
import time
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        word_counts = defaultdict(int)
        for word in words:
            sorted_word = ''.join(sorted(set(word)))
            word_counts[sorted_word] += 1
        
        def get_puzzle_sequences(puzzle):
            first_char = puzzle[0]
            sorted_puzzle = ''.join(sorted(puzzle))
            def helper(i):
                if i == len(puzzle):
                    yield ['']
                    return
                char = sorted_puzzle[i]
                if char == first_char:
                    for sequence in helper(i+1):
                        yield [char] + sequence
                else:
                    for sequence in helper(i+1):
                        yield sequence
                        yield [char] + sequence
                    
            for sequence in helper(0):
                yield ''.join(sequence)
        
        retval = [0] * len(puzzles)
        for i, puzzle in enumerate(puzzles):
            count = 0
            for puzzle_sequence in get_puzzle_sequences(puzzle):
                count += word_counts[puzzle_sequence]
            retval[i] = count
        
        return retval
            
        
\"\"\"
        puzzle_index_set_lookup = defaultdict(set)
        for i, puzzle in enumerate(puzzles):
            for char in puzzle:
                puzzle_index_set_lookup[char].add(i)
        
        cached_puzzle_index_list = {}
        def get_puzzle_index_list(sorted_word):
            puzzle_index_list = cached_puzzle_index_list.get(sorted_word[:4])
            if puzzle_index_list is not None:
                return puzzle_index_list
            for i, char in enumerate(sorted_word[:4]):
                if i == 0:
                    puzzle_index_list = list(puzzle_index_set_lookup[char])
                else:
                    next_puzzle_index_list = []
                    current_puzzle_index_set = puzzle_index_set_lookup[char]
                    for puzzle_index in puzzle_index_list:
                        if puzzle_index in current_puzzle_index_set:
                            next_puzzle_index_list.append(puzzle_index)
                    puzzle_index_list = next_puzzle_index_list
            cached_puzzle_index_list[sorted_word[:4]] = puzzle_index_list
            return puzzle_index_list
        
        retval = [0] * len(puzzles)
        puzzle_sets = [set(puzzle) for puzzle in puzzles]
        for word in words:
            sorted_word = ''.join(sorted(word))
            for puzzle_index in get_puzzle_index_list(sorted_word):
                puzzle_set = puzzle_sets[puzzle_index]
                if puzzles[puzzle_index][0] in word:
                    match = True
                    for char in word:
                        if char not in puzzle_set:
                            match = False
                            break
                    if match:
                        retval[puzzle_index] += 1
        return retval
\"\"\"
    
    
    
    
    
    
    
\"\"\"
    def get_filtered_words(self, words, puzzles):
        filtered_words = defaultdict(list)
        char_counts = defaultdict(int)
        for word in words:
            word_set = set(word)
            for char in word_set:
                char_counts[char] += 1
                filtered_words[char].append(word)
        return filtered_words, char_counts
                
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        print (time.time())
        filtered_words, char_counts = self.get_filtered_words(words, puzzles)
        #print (filtered_words, char_counts)
        print (time.time(), char_counts)
        print (len(words), [len(word_list) for word_list in filtered_words.values()])
        
        def get_max_missing_char(puzzle_set):
            max_missing_char = None
            max_missing_char_count = -1
            for char in string.ascii_lowercase:
                if char in puzzle_set:
                    continue
                # This is a missing char.. identify the one that occurs the most so we can filter it
                missing_char_count = char_counts[char]
                if missing_char_count > max_missing_char_count:
                    max_missing_char_count = missing_char_count
                    max_missing_char = char
            return max_missing_char
        
        double_filtered_words = defaultdict(lambda: defaultdict(list))
        for first_char, word_list in filtered_words.items():
            for word in word_list:
                word_set = set(word)
                for missing_char in string.ascii_lowercase:
                    if missing_char not in word_set:
                        double_filtered_words[first_char][missing_char].append(word)
        #print(double_filtered_words)
        print(time.time())
        for char, missing_char_dict in double_filtered_words.items():
            print(char, [len(word_list) for word_list in missing_char_dict.values()])
        return
        
        retval = []
        for puzzle in puzzles:
            puzzle_set = set(puzzle)
            count = 0
            #print (puzzle, get_max_missing_char(puzzle_set), double_filtered_words[puzzle[0]][get_max_missing_char(puzzle_set)])
            for word in double_filtered_words[puzzle[0]][get_max_missing_char(puzzle_set)]:
                match = True
                for char in word:
                    if char not in puzzle_set:
                        match = False
                        break
                if match:
                    count += 1
            retval.append(count)
        return retval
        
\"\"\"
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
\"\"\"
        retval = []
        for puzzle in puzzles:
            puzzle_set = set(puzzle)
            first_char = puzzle[0]
            count = 0
            for word in words:
                found_first_char = False
                found_all_chars = True
                for char in word:
                    if char == first_char:
                        found_first_char = True
                    elif char not in puzzle_set:
                        found_all_chars = False
                        break
                if found_first_char and found_all_chars:
                    count += 1
            retval.append(count)
        return retval
\"\"\"

def to_mask(word):
    ret = 0
    for c in word:
        ret |= 1 << (ord(c) - 97)
    return ret

def get_good_masks(word):
    BASE = 1 << (ord(word[0]) - 97)
    ret = []
    
    for choice in range(64):
        mask = BASE
        for i in range(6):
            if (1 << i) & choice:
                mask |= 1 << (ord(word[i+1]) - 97)
        ret.append(mask)
        
    return ret

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        # Construct bitmask frequency hashtable
        mask_frequency = defaultdict(int)
        for word in words:
            mask_frequency[to_mask(word)] += 1
            
        # Calculate
        N = len(puzzles)
        ans = [0] * N
        for i, puzzle in enumerate(puzzles):
            for mask in get_good_masks(puzzle):
                ans[i] += mask_frequency[mask]
        
        return ans

class Puzzle:
    def __init__(self, puzzle):
        self.first_letter = puzzle[0]
        self.puzzle = set(puzzle)
        
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = collections.Counter(frozenset(w) for w in words)
        res = [0] * len(puzzles)
        for i, puzzle in enumerate(puzzles):
            subsets = [puzzle[0]]
            for c in puzzle[1:]:
                subsets += [sub + c for sub in subsets]
            res[i] += sum(cnt[frozenset(sub)] for sub in subsets)
        return res
            
                    


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

            mp[mask]+=1
        # print(mp)
        res = []
        for p in puzzles:
            lenp = len(p)-1
            cnt = 0
            for i in range(1<<lenp):
                mask = 1<<(ord(p[0])-ord('a'))
                for j in range(lenp):
                    if i & (1<<j):
                        mask|=(1<<(ord(p[j+1])-ord('a')))

                # print('mp', mp, 'mask', mask)
                if mp[mask]:
                    cnt+=mp[mask]


            res.append(cnt)

        return res

        
#         res = [0]*len(puzzles)
#         lswords = [set()]*len(words)
#         for idx, word in enumerate(words):
#             lswords[idx] = set(word)
      
#         # print('lisr of set words',lswords)
#         for idx, puzzle in enumerate(puzzles):
#             firstLetter = puzzle[0]
#             remLetters = set(puzzle)

#             cnt = 0
#             # print(puzzle, firstLetter, remLetters)
#             for sWord in lswords:
#                 # print(word, 'sword',sWord,'\
')
#                 if firstLetter in sWord and sWord.issubset(remLetters):
#                     # print('inc')
#                     cnt+=1

#             res[idx]=cnt
#             # print('end of puzzle\
\
')
#         return res


from itertools import combinations

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]):
        def code_word(word):
            b = 0
            for c in word:
                b |= 1 << (ord(c) - ord('a'))
            return b
        
        def remove_duplicates(word):
            d = {}
            result = \"\"
            for c in word:
                if c not in d:
                    d[c] = True
                    result += c
            return result
                    
        
        words_bits = defaultdict(int)   
        for word in words:
            b = code_word(word)
            words_bits[b] += 1
            
        for puzzle in puzzles:
            count = 0
            first_letter = 1 << (ord(puzzle[0]) - ord('a'))       
            if not first_letter & code_word(puzzle):
                continue
            p = remove_duplicates(puzzle)
            for i in range(len(p)):
                for c in combinations(p,i + 1):
                    b = code_word(c)
                    if b in words_bits and first_letter & b:
                        count += words_bits[b]
            yield count
        
                
        

from itertools import combinations

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]):
        def code_word(word):
            b = 0
            for c in word:
                b |= 1 << (ord(c) - ord('a'))
            return b
        
        def remove_duplicates(word):
            d = {}
            result = \"\"
            for c in word:
                if c not in d:
                    d[c] = True
                    result += c
            return result
        
        words_bits = defaultdict(int)   
        for word in words:
            b = code_word(word)
            words_bits[b] += 1
            
        for puzzle in puzzles:
            count = 0
            first_letter = 1 << (ord(puzzle[0]) - ord('a'))       
            if not first_letter & code_word(puzzle):
                continue
            p = remove_duplicates(puzzle)
            for i in range(len(p)):
                for c in combinations(p,i + 1):
                    b = code_word(c)
                    if b in words_bits and first_letter & b:
                        count += words_bits[b]
            yield count
        
                
        

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(len(p)):
                for c in itertools.combinations(p[1:], k):
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

    def findNumOfValidWords2(self, words, puzzles):
        count = collections.Counter()
        for w in words:
            if len(set(w)) > 7: continue
            m = 0
            for c in w:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
        res = []
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - 97)]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - 97) for m in bfs]
            res.append(sum(count[m] for m in bfs))
        return res
    
    def getBitMask(self, word: str) -> int:
        mask = 0
        for c in word:
\t\t    # Maps 'a' -> 0, 'b' -> 1, 'c' -> 2, ...
            i = ord(c) - ord('a')
\t\t\t# Sets the i-th bit to 1.
            mask |= 1 << i
        return mask

    def findNumOfValidWords1(self, words: List[str], puzzles: List[str]) -> List[int]:
\t    # [2]
\t\t# Maps the bit mask for every word to the count of words with that same bit mask.
\t\t# For example 'abd' and 'baddd' would have the same mask because they are composed
\t\t# of the same set of characters.
        letterFrequencies = {}
        for word in words:
            mask = self.getBitMask(word)
            letterFrequencies[mask] = letterFrequencies.get(mask, 0) + 1
        
        solution = [0] * len(puzzles)
        
        for i in range(len(puzzles)):
            puzzle = puzzles[i]
            mask = self.getBitMask(puzzle)
            subMask = mask
            total = 0
\t\t\t
\t\t\t# The index of the first bit in the puzzle. We need this to check if the
\t\t\t# submasks we generate are of valid words.
            firstBitIndex = ord(puzzle[0]) - ord('a')

\t\t\t# [3]
            # In this while loop we want to go through all possible \"submasks\" of the bit
\t\t\t# mask for the current puzzle. If our puzzle bit mask is 1011, for example, we
\t\t\t# would generate 1011, 1010, 1001, 1000, 0011, 0010, 0001, 0000
            while True:
\t\t\t\t# [4]
\t\t\t    # If this submask contains the first letter of the puzzle, it's a valid word. Here
\t\t\t\t# we add to the number of words we've seen with this mask to our total.
                if subMask >> firstBitIndex & 1:
                    total += letterFrequencies.get(subMask, 0)
\t\t\t\t# We've exhausted all possible submasks.
                if subMask == 0:
                    break
\t\t\t\t# Get rid of the right-most bit, and restore any bits to the right of it that were
\t\t\t\t# originally in the mask. If the original mask was '01011' current submask is '01000',
\t\t\t\t# then submask - 1 = '00111' and (submask - 1) & mask = '00011'.
                subMask = (subMask - 1) & mask
            solution[i] = total
        
        return solution

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def getNum(s: str) -> int:
            res = 0
            for c in s:
                res |= (1 << (ord(c) - 97))
            return res
        
        counter = Counter([getNum(set(word)) for word in words if len(set(word)) < 8])
        ans = []
        for puzzle in puzzles:
            sub = [(1 << (ord(puzzle[0]) - 97))]
            for c in puzzle[1:]:
                sub += [m | (1 << (ord(c) - 97)) for m in sub]
            ans.append(sum(counter[w] for w in sub))
            
        return ans

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = defaultdict(int)
        result = [0 for _ in range(len(puzzles))]
        
        def dfs(puzzle, i, trie, hasFirst=False):        
            if \"*\" in trie and hasFirst:
                result[i] += trie[\"*\"]
                        
            for c in puzzle:
                if c in trie:
                    dfs(puzzle, i, trie[c], hasFirst or c == puzzle[0])
                            
        for w in words:
            curr = trie
            for c in sorted(set(w)):
                curr = curr.setdefault(c, defaultdict(int))
              
            curr[\"*\"] += 1
            # if \"*\" in curr:
            #     curr[\"*\"] += 1
            # else:
            #     curr[\"*\"] = 1
                        
        for i, p in enumerate(puzzles):
            dfs(p, i, trie)
            
        return result

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def helper(mask,pIdx,i):
            str1=puzzles[pIdx]
            if i>=len(str1):
                return
            mask2=mask
            mask2|=1<<(ord(str1[i])-ord('a'))
            if mask2^mask:
                d[mask2].add(pIdx)
                helper(mask2,pIdx,i+1)
            helper(mask,pIdx,i+1)

        d=collections.defaultdict(set)
        n=len(puzzles)
        for i,p in enumerate(puzzles):
            mask=1<<(ord(p[0])-ord('a'))
            d[mask].add(i)
            helper(mask,i,1)
        res=[0]*len(puzzles)
        for w in words:
            mask=0
            for c in w:
                mask|=1<<(ord(c)-ord('a'))
            for idx in d[mask]:
                res[idx]+=1
        return res

from collections import defaultdict

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        d = defaultdict(int)
        for word in words:
            wl = list(set(list(word)))
            wl.sort()
            d[''.join(wl)] += 1
        ans = []
        
        for puzzle in puzzles:
            f = puzzle[0]
            pl = sorted(list(puzzle))
            fi = pl.index(f)
            tmp = 0
            for i in range(2 ** (len(pl) - 1)):
                cand = []
                for j in range(len(pl)):
                    if j < fi:
                        if i & (1 << j):
                            cand.append(pl[j])
                    elif j == fi:
                        cand.append(f)
                    else:
                        if i & (1 << (j - 1)):
                            cand.append(pl[j])
                cs = ''.join(cand)
                tmp += d[cs]
            ans.append(tmp)
        
        return ans
        
        


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        class TrieNode():
            def __init__(self):
                self.children = collections.defaultdict(TrieNode)
                self.word_inds = []
                
            def add(self, x, word_ind):
                if x:
                    self.children[x[0]].add(x[1:], word_ind)
                else:
                    self.word_inds.append(word_ind)
        
        root = TrieNode()
                
        for ind, word in enumerate(words):
            root.add(sorted(set(word)), ind)
            
        counts = []
        for puzzle in puzzles:
            nodes = [root]
            for letter in sorted(puzzle):
                new_nodes = []
                for node in nodes:
                    if letter in node.children:
                        new_nodes.append(node.children[letter])
                nodes += new_nodes
            count = 0
            for node in nodes:
                for word_ind in node.word_inds:
                    if puzzle[0] in words[word_ind]:
                        count += 1
            counts.append(count)
        
        return counts
                
            
                    
                    


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        wordPatternCnt = collections.defaultdict(int)
        
        for word in words:
            pattern = 0
            for letter in word:
                pattern |= (1 << ord(letter) - ord(\"a\"))
            wordPatternCnt[pattern] += 1
        
        res = []
        
        for puzzle in puzzles:
            cnt = 0
            pattern = 0
            for letter in puzzle:
                pattern |= (1 << (ord(letter) - ord(\"a\")))
                
            subPattern = pattern
                
            while subPattern > 0:
                if subPattern & (1 << (ord(puzzle[0]) - ord(\"a\"))): #valid pattern must conclude the first letter of puzzle
                    cnt += wordPatternCnt[subPattern]
                    
                subPattern = pattern & (subPattern - 1)
            
            res.append(cnt)
        
        return res
                

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = Counter(frozenset(w) for w in words if len(set(w)) <= 7)
        ans = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for i in itertools.combinations(p[1:], k):
                    cur += cnt[frozenset((p[0],) + i)]
            ans.append(cur)
        return ans
                    
        
        
#         ans = []
#         cnt = Counter()
#         for w in words:
#             w = set(w)
#             if len(w) > 7:
#                 continue
#             w_bit = 0
#             for c in w:
#                 w_bit |= 1 << ord(c) - ord('a')
#             cnt[w_bit] += 1
#         for p in puzzles:
#             bfs = [1 << ord(p[0]) - ord('a')]
#             for c in p[1:]:
#                 bfs += [m | 1 << ord(c) - ord('a') for m in bfs]
#             ans.append(sum(cnt[m] for m in bfs))
#         return ans


class Node:
    def __init__(self):
        self.ch = {}
        self.cnt = 0
    def build(self, words):
        for w in words:
            n = self
            for c in w:
                if c not in n.ch:
                    n.ch[c] = Node()
                n = n.ch[c]
            n.cnt += 1
    def search(self, w, first):
        ans = 0
        if first:
            ans += self.cnt
        for c in w:
            if c not in self.ch:
                continue
            if c == w[0]:
                ans += self.ch[c].search(w, True)
            else:
                ans += self.ch[c].search(w, first)
        return ans
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        root = Node()
        root.build([sorted(set(x)) for x in words])
        ans = []
        for p in puzzles:
            ans.append(root.search(p, False))
        return ans
            
            


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        counter = Counter()
        res = []
        for w in words:
            bitmask = 0
            for c in set(w):
                bitmask |= 1 << ord(c)-ord('a')
            counter[bitmask] += 1
            
        for p in puzzles:
            cands = [1<<ord(p[0])-ord('a')]
            for c in p[1:]:
                cands += [b|(1<<ord(c)-ord('a')) for b in cands]

            res.append(sum(counter[b] for b in cands))
            
        return res
            


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        count = collections.Counter(frozenset(w) for w in words)
        res = []
        for p in puzzles:
            cur = 0
            for k in range(7):
                for c in itertools.combinations(p[1:], k):
                    cur += count[frozenset(tuple(p[0]) + c)]
            res.append(cur)
        return res

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        # Trie
        trie = {}
        ans = [0] * len(puzzles)
        for word in words:
            cur = trie
            for w in sorted(set(word)):
                if w not in cur:
                    cur[w] = {}
                cur = cur[w]
            if '#' not in cur:
                cur['#'] = 1
            else:
                cur['#'] += 1
                
        def dfs(cur, i, head):
            p = puzzles[i]
            if '#' in cur and head:
                ans[i] += cur['#']
            for c in cur:
                if c in p:
                    if p[0] == c or head:
                        dfs(cur[c], i, True)
                    else:
                        dfs(cur[c], i, False)
            return
        
        for i in range(len(puzzles)):
            dfs(trie, i, False)
            
        return ans
        
        
        
        # # Using build-in combinations
        # cnt = Counter(frozenset(w) for w in words if len(set(w)) <= 7)
        # ans = []
        # for p in puzzles:
        #     cur = 0
        #     for k in range(7):
        #         for i in itertools.combinations(p[1:], k):
        #             cur += cnt[frozenset((p[0],) + i)]
        #     ans.append(cur)
        # return ans
                    
        
        # # bit-mask & bfs-based combinations
        # ans = []
        # cnt = Counter()
        # for w in words:
        #     w = set(w)
        #     if len(w) > 7:
        #         continue
        #     w_bit = 0
        #     for c in w:
        #         w_bit |= 1 << ord(c) - ord('a')
        #     cnt[w_bit] += 1
        # for p in puzzles:
        #     bfs = [1 << ord(p[0]) - ord('a')]
        #     for c in p[1:]:
        #         bfs += [m | 1 << ord(c) - ord('a') for m in bfs]
        #     ans.append(sum(cnt[m] for m in bfs))
        # return ans


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def generate(n):
            res = [0]
            cur = 1
            while n:
                if n & 1 == 1:
                    res += [i + cur for i in res]
                n >>= 1
                cur <<= 1
            return set(res)
        def to_bit(w):
            res = 0
            for c in w:
                res |= 1 << (ord(c) - ord('a'))
            return res
        m = collections.defaultdict(dict)
        for w in words:
            visited = set()
            for c in w:
                if c in visited: continue
                visited.add(c)
                b = to_bit(w)
                if b not in m[c]:
                    m[c][b] = 1
                else:
                    m[c][b] += 1
        res = []
        for w in puzzles:
            s1, count = m[w[0]], 0
            for i in generate(to_bit(w)):
                if i in s1: 
                    count += s1[i]
            res.append(count)
        
        return res

from functools import reduce
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        
        # Trie
        ans = [0] * len(puzzles)
        T = lambda: collections.defaultdict(T)
        trie = T()
        for w in words:
            cur = reduce(dict.__getitem__, sorted(set(w)), trie)
            if '#' not in cur:
                cur['#'] = 1
            else:
                cur['#'] += 1
                
        def dfs(cur, i, head):
            p = puzzles[i]
            if '#' in cur and head:
                ans[i] += cur['#']
            for c in cur:
                if c in p:
                    if p[0] == c or head:
                        dfs(cur[c], i, True)
                    else:
                        dfs(cur[c], i, False)
            return
        
        for i in range(len(puzzles)):
            dfs(trie, i, False)
            
        return ans
        
        
        
        # # Using build-in combinations
        # cnt = Counter(frozenset(w) for w in words if len(set(w)) <= 7)
        # ans = []
        # for p in puzzles:
        #     cur = 0
        #     for k in range(7):
        #         for i in itertools.combinations(p[1:], k):
        #             cur += cnt[frozenset((p[0],) + i)]
        #     ans.append(cur)
        # return ans
                    
        
        # # bit-mask & bfs-based combinations
        # ans = []
        # cnt = Counter()
        # for w in words:
        #     w = set(w)
        #     if len(w) > 7:
        #         continue
        #     w_bit = 0
        #     for c in w:
        #         w_bit |= 1 << ord(c) - ord('a')
        #     cnt[w_bit] += 1
        # for p in puzzles:
        #     bfs = [1 << ord(p[0]) - ord('a')]
        #     for c in p[1:]:
        #         bfs += [m | 1 << ord(c) - ord('a') for m in bfs]
        #     ans.append(sum(cnt[m] for m in bfs))
        # return ans


import string
from collections import defaultdict
import time
class Node:
    def __init__(self, char):
        self.char = char
        self.count = 0
        self.children = {}
    def add_word(self, word):
        current = self
        for char in word:
            current = current.children.setdefault(char, Node(char))
        current.count += 1
        
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        trie = Node(None)
        for word in words:
            sorted_word = ''.join(sorted(set(word)))
            trie.add_word(sorted_word)
            
        def get_word_count(puzzle):
            first_char = puzzle[0]
            sorted_puzzle = ''.join(sorted(puzzle))
            count = 0
            def helper(i, node):
                if i == len(puzzle):
                    yield node
                    return
                char = sorted_puzzle[i]
                if char == first_char:
                    if char in node.children:
                        for yielded_node in helper(i+1, node.children[char]):
                            yield yielded_node
                else:
                    for yielded_node in helper(i+1, node):
                        yield yielded_node
                    if char in node.children:
                        for yielded_node in helper(i+1, node.children[char]):
                            yield yielded_node

            for yielded_node in helper(0, trie):
                count += yielded_node.count
            return count
        
        retval = [0] * len(puzzles)
        for i, puzzle in enumerate(puzzles):
            retval[i] = get_word_count(puzzle)
        
        return retval
            
        
\"\"\"
        puzzle_index_set_lookup = defaultdict(set)
        for i, puzzle in enumerate(puzzles):
            for char in puzzle:
                puzzle_index_set_lookup[char].add(i)
        
        cached_puzzle_index_list = {}
        def get_puzzle_index_list(sorted_word):
            puzzle_index_list = cached_puzzle_index_list.get(sorted_word[:4])
            if puzzle_index_list is not None:
                return puzzle_index_list
            for i, char in enumerate(sorted_word[:4]):
                if i == 0:
                    puzzle_index_list = list(puzzle_index_set_lookup[char])
                else:
                    next_puzzle_index_list = []
                    current_puzzle_index_set = puzzle_index_set_lookup[char]
                    for puzzle_index in puzzle_index_list:
                        if puzzle_index in current_puzzle_index_set:
                            next_puzzle_index_list.append(puzzle_index)
                    puzzle_index_list = next_puzzle_index_list
            cached_puzzle_index_list[sorted_word[:4]] = puzzle_index_list
            return puzzle_index_list
        
        retval = [0] * len(puzzles)
        puzzle_sets = [set(puzzle) for puzzle in puzzles]
        for word in words:
            sorted_word = ''.join(sorted(word))
            for puzzle_index in get_puzzle_index_list(sorted_word):
                puzzle_set = puzzle_sets[puzzle_index]
                if puzzles[puzzle_index][0] in word:
                    match = True
                    for char in word:
                        if char not in puzzle_set:
                            match = False
                            break
                    if match:
                        retval[puzzle_index] += 1
        return retval
\"\"\"
    
    
    
    
    
    
    
\"\"\"
    def get_filtered_words(self, words, puzzles):
        filtered_words = defaultdict(list)
        char_counts = defaultdict(int)
        for word in words:
            word_set = set(word)
            for char in word_set:
                char_counts[char] += 1
                filtered_words[char].append(word)
        return filtered_words, char_counts
                
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        print (time.time())
        filtered_words, char_counts = self.get_filtered_words(words, puzzles)
        #print (filtered_words, char_counts)
        print (time.time(), char_counts)
        print (len(words), [len(word_list) for word_list in filtered_words.values()])
        
        def get_max_missing_char(puzzle_set):
            max_missing_char = None
            max_missing_char_count = -1
            for char in string.ascii_lowercase:
                if char in puzzle_set:
                    continue
                # This is a missing char.. identify the one that occurs the most so we can filter it
                missing_char_count = char_counts[char]
                if missing_char_count > max_missing_char_count:
                    max_missing_char_count = missing_char_count
                    max_missing_char = char
            return max_missing_char
        
        double_filtered_words = defaultdict(lambda: defaultdict(list))
        for first_char, word_list in filtered_words.items():
            for word in word_list:
                word_set = set(word)
                for missing_char in string.ascii_lowercase:
                    if missing_char not in word_set:
                        double_filtered_words[first_char][missing_char].append(word)
        #print(double_filtered_words)
        print(time.time())
        for char, missing_char_dict in double_filtered_words.items():
            print(char, [len(word_list) for word_list in missing_char_dict.values()])
        return
        
        retval = []
        for puzzle in puzzles:
            puzzle_set = set(puzzle)
            count = 0
            #print (puzzle, get_max_missing_char(puzzle_set), double_filtered_words[puzzle[0]][get_max_missing_char(puzzle_set)])
            for word in double_filtered_words[puzzle[0]][get_max_missing_char(puzzle_set)]:
                match = True
                for char in word:
                    if char not in puzzle_set:
                        match = False
                        break
                if match:
                    count += 1
            retval.append(count)
        return retval
        
\"\"\"
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
        
\"\"\"
        retval = []
        for puzzle in puzzles:
            puzzle_set = set(puzzle)
            first_char = puzzle[0]
            count = 0
            for word in words:
                found_first_char = False
                found_all_chars = True
                for char in word:
                    if char == first_char:
                        found_first_char = True
                    elif char not in puzzle_set:
                        found_all_chars = False
                        break
                if found_first_char and found_all_chars:
                    count += 1
            retval.append(count)
        return retval
\"\"\"

class TrieNode:
    def __init__(self):
        self.children = [None] *26
        self.count = 0

class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        self.root = TrieNode()
        for word in words:
            chars = sorted(set(list(word)))
            temp = \"\".join(chars)
            self.insert(temp)
        ans = []
        for puzzle in puzzles:
            ans.append(self.dfs(puzzle,self.root,False))
        return ans


    def dfs(self,puzzle,temp,collect = False):
        if not temp:
            return 0
        
        ans = temp.count if collect else 0
        
        for c in puzzle:
            index = ord(c) - ord('a')
            if temp.children[index]:
                ans += self.dfs(puzzle,temp.children[index], collect or c == puzzle[0])
        return ans
    
    def insert(self,word):
        temp = self.root
        for i in range(len(word)):
            index = ord(word[i]) - ord('a')
            if not temp.children[index]:
                temp.children[index] = TrieNode()
            temp = temp.children[index]
        temp.count += 1
        

class Solution:
    def findNumOfValidWords(self, words, puzzles):
        count = collections.Counter()
        for w in words:
            if len(set(w)) > 7: continue
            m = 0
            for c in w:
                m |= 1 << (ord(c) - 97)
            count[m] += 1
        res = []
        for p in puzzles:
            bfs = [1 << (ord(p[0]) - 97)]
            for c in p[1:]:
                bfs += [m | 1 << (ord(c) - 97) for m in bfs]
            res.append(sum(count[m] for m in bfs))
        return res

class Puzzle:
    def __init__(self, puzzle):
        self.first_letter = puzzle[0]
        self.puzzle = set(puzzle)
        
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        cnt = collections.Counter(frozenset(w) for w in words)
        res = [0] * len(puzzles)
        for i, puzzle in enumerate(puzzles):
            for bin_i in range(2**6, 2**7):
                mask = bin(bin_i)[2:]
                subset = frozenset([puzzle[j] for j in range(7) if mask[j] == '1'])
                res[i] += cnt[subset]
        return res
            
                    


class Node:
    def __init__(self):
        self.ch = {}
        self.cnt = 0
    def build(self, words):
        for w in words:
            n = self
            for c in w:
                if c not in n.ch:
                    n.ch[c] = Node()
                n = n.ch[c]
            n.cnt += 1
    def search(self, w, first):
        ans = 0
        if first:
            ans += self.cnt
        for c in w:
            if c not in self.ch:
                continue
            if c == w[0]:
                ans += self.ch[c].search(w, True)
            else:
                ans += self.ch[c].search(w, first)
        return ans
class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        root = Node()
        root.build([set(x) for x in words])
        ans = []
        for p in puzzles:
            ans.append(root.search(p, False))
        return ans
            
            


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        def binarize(word):
            ans = 0
            for c in word:
                ans |= (1 << (ord(c) - ord(\"a\")))
            ans = bin(ans)[2:]
            return \"0\" * (26 - len(ans)) + ans
        
        words = [binarize(word) for word in words if len(set(word)) < 8]
        trie = {}
        for i, word in enumerate(words):
            temp = trie
            for c in word:
                if c not in temp:
                    temp[c] = {}
                temp = temp[c]
            if \"*\" not in temp:
                temp[\"*\"] = []
            temp[\"*\"] += [i]
            
        puzzles = [(puzzle[0], binarize(puzzle)) for puzzle in puzzles]
        ans = []
        for c, puzzle in puzzles:
            tries = [trie]
            for b in puzzle:
                new_tries = []
                
                for temp in tries:
                    if \"0\" in temp:
                        new_tries += [temp[\"0\"]]
                    if b == \"1\" and \"1\" in temp:
                        new_tries += [temp[\"1\"]]
                        
                tries = new_tries
                
            count = 0
            for temp in tries:
                for i in temp[\"*\"]:
                    if words[i][25 - ord(c) + ord(\"a\")] == \"1\":
                        count += 1
            ans += [count]
            
        return ans

from collections import defaultdict
from typing import List


def get_encode(word, letters):
    encode = ['0'] * 26
    for c in word:
        idx = letters.index(c)
        encode[idx] = '1'
    return ''.join(encode)


def dfs(encode, cur, sub_encodes):
    if cur == len(encode):
        sub_encodes.add(encode)
        return
    elif encode[cur] == '1':
        sub_zero = encode[:cur] + '0' + encode[cur+1:]
        sub_one = encode[:cur] + '1' + encode[cur+1:]
        sub_encodes.add(sub_zero)
        sub_encodes.add(sub_one)
        dfs(sub_zero, cur+1, sub_encodes)
        dfs(sub_one, cur+1, sub_encodes)
    else:
        dfs(encode, cur+1, sub_encodes)


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        letters = 'abcdefghijklmnopqrstuvwxyz'
        records = defaultdict(int)
        for word in words:
            encode = get_encode(word, letters)
            records[encode] += 1

        results = []
        for puzzle in puzzles:
            encode, cur, idx_first = get_encode(puzzle, letters), 0, letters.index(puzzle[0])
            sub_encodes = {encode}
            dfs(encode, cur, sub_encodes)
            result = sum([records[sub_encode] for sub_encode in list(sub_encodes) if sub_encode[idx_first] == '1'])
            results.append(result)
        return results


class Solution:
    def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
        dic = {} # trie
        for word in words:
            cur = dic
            for c in word:
                if c not in cur:
                    cur[c]={}
                cur = cur[c]
            if '*' not in cur:
                cur['*']=1
            else:
                cur['*']+=1
        res = [0 for _ in range(len(puzzles))]
        def dfs(i, dic, check_head):
            puzzle =puzzles[i]
            if '*' in dic and check_head:
                res[i]+=dic['*']
            for k in dic:
                if k in puzzle:
                    if puzzle[0]==k or check_head:
                        dfs(i, dic[k], True)
                    else:
                        dfs(i, dic[k], False)
                
                    
        for i in range(len(puzzles)):
            dfs(i, dic, False)
        return res