# LeetCode: 1178. 猜字谜¶

## 1、题目描述¶

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

1 个单词可以作为 "aboveyz" 的谜底 : "aaaa"
1 个单词可以作为 "abrodyz" 的谜底 : "aaaa"
3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able"
2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas"
4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access"



• 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] 都是小写英文字母。
• 每个 puzzles[i] 所包含的字符都不重复。

## 2、解题思路¶

• 使用位运算
• 每一个小写字母看成是1左移n位
• 首先将所有的谜底都进行位或运算
• 由于谜面的长度不会超过7，所以可以直接生成谜面的所有的子集

j = temp
while j:
j = (j - 1) & temp


temp开始减小，不断地找出下一个满足条件的子集

class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
import string
from collections import defaultdict

mapping = {}

for index, c in enumerate(string.ascii_lowercase):
mapping[c] = 1 << index

words_bit = defaultdict(int)

for word in words:
temp = 0
for c in word:
temp |= mapping[c]
words_bit[temp] += 1

res = [0] * len(puzzles)

for index, puzzle in enumerate(puzzles):
# 谜面的二进制形式
temp = 0
for c in puzzle:
temp |= mapping[c]

# 生成所有的谜面子集
j = temp
while j:
if (mapping[puzzle[0]]) & j:
res[index] += words_bit[j]
j = (j - 1) & temp
return res