裸的方法很容易想到,用二进制来压缩状态,暴力。
容易观察到 puzzles的长度很短,只有7。
因此可以把puzzle的mask算出来,然后去枚举所有的子状态。。
discuss里给出了一种方法,比如mask是 01001
那么可以这样遍历他的子状态(注意这里漏了全0的情况)
submask := mask
for submask > 0 {
//do some operation
submask = (submask-1) & mask
}
func findNumOfValidWords(words []string, puzzles []string) []int {
cnt := make(map[int]int)
for i := 0; i < len(words); i++ {
tmp := 0
for j := 0; j < len(words[i]); j++ {
tmp |= 1 << int(words[i][j] - 'a')
}
cnt[tmp]++
}
ans := make([]int, len(puzzles))
for i := 0; i < len(puzzles); i++ {
mask := 0
for j := 1; j < len(puzzles[i]); j++ {
mask |= 1 << int(puzzles[i][j] - 'a')
}
first := 1 << int(puzzles[i][0] - 'a')
code := mask
for code > 0 {
ans[i] += cnt[code|first]
code = (code - 1) & mask
}
ans[i] += cnt[first]
}
return ans
}