# LeetCode 1178.猜字谜

## 题目描述

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] 都是小写英文字母。



## 题解

1. 谜面的第一个字母必须在谜底中存在
2. 谜底的所有字母必须在谜面中存在

1. 固定首先第一位字符必须存在
2. 剩下的字符可能出现也可能不出现，共有 $2^6=64$ 种可能

1. 把所有谜底编码成整数，并统计每个整数对应的个数
2. 把谜面对应的 $64$ 种可能枚举出来，计算相应的谜底个数

## 代码

### go

import (
"math/bits"
)

func findNumOfValidWords(words []string, puzzles []string) []int {
m := make(map[int]int)
for _, word := range words{
num := 0
for _, c := range(word) {
num |= 1<<(c - 'a')
}
if bits.OnesCount(uint(num)) <= 7 {
m[num]++
}
}
res := make([]int, len(puzzles))
for idx, puzzle := range(puzzles) {
count := 0
for i:=0; i<(1<<6); i++ {
temp := 1 << (puzzle[0] - 'a')
for j:=0; j<6; j++ {
temp |= ((i >> j) & 1)<<(puzzle[j+1] - 'a')
}
count += m[temp]
}
res[idx] = count
}
return res
}


### python

class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
def w2n(s):
num = 0
for c in s:
num |= 1<<(ord(c) - ord('a'))
return num

m = {}
for word in words:
if len(ws := set(word)) <= 7:
w = w2n(ws)
m[w] = m.get(w, 0) + 1

def getRes(puzzle):
count = 0
lst = [ord(c) - ord('a') for c in puzzle]
# 枚举所有可能的谜面
for i in range(1<<6):
temp = 1 << lst[0]
for j in range(6):
temp |= (((i>>j) & 1) << lst[j+1])
count += m.get(temp, 0)
return count
return [getRes(puzzle) for puzzle in puzzles]