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.

Source: leetcode | Difficulty: MEDIUM
Tags: String algorithms

Bit manipulation

Data structures

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]:
		orda = ord('a')
		mask = defaultdict(int)
		for w in words:
			m = 0
			for c in w:
				m |= 1 << ord(c) - orda
			mask[m] += 1
		res = []
		for p in puzzles:
			ones = []
			for c in p:
				ones.append(1 << ord(c) - orda)
			valid = [ones[0]]
			for i in range(1, 7):
				valid.extend([ones[i] + v for v in valid])
			novw = 0
			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]:
		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


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:

	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]:
		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((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(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]:
		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]:

		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, 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 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)}
		word_masks = {}
		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


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 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


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


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 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


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]:
		mask_frequency = defaultdict(int)
		for word in words:
			mask_frequency[to_mask(word)] += 1
		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]:

		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)
					elif 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]:
		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


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]:
		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


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]:
		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


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


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 = {}
		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