1178. 猜字谜
这是今天的打卡题，我打开一看标签是困难，心里咯噔一声，觉得完蛋，今天我肯定做不出来了。事实也确实如此。
这道题的意思是，给出一个 word，和一个 puzzle，然后判断 word 是不是 puzzle 的一个解。满足的条件是 puzzle 的第一个字母在 word 中出现，然后就是 word 中的每个字母，都在 puzzle 中出现。没有顺序的约定，也没有频次的约定。
看起来似乎不那么难，于是我写了这样的代码：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
# 初始化答案数组
result = {}
for p in puzzles:
result[p] = 0
sets = {}
for w in words:
for p in puzzles:
if p in sets:
p_set = sets[p]
else:
p_set = set([i for i in p])
sets[p] = p_set
first_c = False
c_c = True
for c in w:
#检查第一个字母
if c == p[0]:
first_c = True
if c not in p_set:
c_c = False
break
if first_c and c_c:
result[p] += 1
return [ result[key] for key in puzzles ]
果断写了一个 O(m*n) 的算法，也是可以跑出第一个用例的答案的，不过颤抖吧少年，这道题的精髓在“提示”里面，words 这个列表的长度有 10^5，而 puzzle 的列表长度 10^4，如果，按照上面的算法，不要侥幸，肯定是 10^9 次比较，不知道算到哪年能算出来了。在这里等着呢。
好吧，只能看答案了。原来这道题目的套路叫“状态压缩”，我自己主动放弃的一个已知条件是，“没有顺序也没有频率的要求”，与其说是“放弃”，不如说是“不会用”。还有个条件是，word 和 puzzle 里只会出现小写字母。然后这题目就成了判断 word 里出现的字母，是不是都在 puzzle 里有，至于 word 里每个字母出现位置和次数都不重要了。
因为字母一共只有 26 个，所以我用一个 26 个 bit 的位图，就可以表达每个字母的有无了。一个整型是 32 位，正好可以用一个整数表达。于是，所有的 word 都可以表达成一个整数的位图。显然有些 word 虽然字面不一样，表达成位图后是一样的。于是我们可以用一个字典记录下来次数。
接下去，第二个任务就是怎么把 puzzle 也表达成位图，然后去字典里查表就可以了。因为 puzzle 也只不过是一个字母的集合，word 包含的字母只要是任何一个 puzzle 的非空子集，就算是合法解了。这里留了一个小曲折，就是必须包含 puzzle 的第一个字母。那就变成了，除去 puzzle 的第一个字母外的所有子集（含空子集），与第一个字母（也是一个子集）的并集。总归是一个求子集的问题。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
freq = collections.Counter()
for w in words :
bitmap = 0
for c in w :
bitmap = 1 << ord(c) - ord('a')
freq[bitmap] += 1
ans = []
for p in puzzles :
total = 0
mask = 0
for c in p[1:] :
mask = 1 << ord(c) - ord('a')
s = 1 << ord(p[0]) - ord('a')
total += freq[s]
subset = mask
while subset > 0:
total += freq[s subset]
subset = ( subset - 1 ) & mask
ans.append(total)
return ans
参考答案，我写出了这样的算法。这里有几个点，第一，用到了一个数据结构叫 Counter，我以前没用过，只会用 dict，其实就是一个内置的封装，没想到还挺好用的，以后可以多用用。这种计数性质的任务还挺多的。
第二，比较神奇的是 23 - 25 行代码，这里展示了一个求二进制数字的子集的方法。这个方法，简直神了，我网上搜了一下，解释得比较清楚的是这篇文章，基本陈述了这个算法的推理过程和原理。虽然我也没有看得很懂，但是比官方题解好多了。
第三，有个优化点我没写，就是题目有个已知条件，puzzle 一共只有 7 个字母，每个字母都不一样，如果 word 的 bitmap 里面的 1 的数量超过七个，其实不用加入到 freq 这个 Counter 里面了，可以节省一点空间，不过因为这个是 O(1) 的查询复杂度，其实对性能影响微乎其微。
这第二个写法，基本的复杂度是 O(m + n) 的，这里 m 和 n 肯定是有系数的，比如，每个 word 的长度是不超过 50，对于每个 puzzle， 有 7 个字母，所以子集的数量有 2^6 个（第一个字母都包含），这个就是 n 的常数系数了。空间复杂度是 O(m) 的。
位运算技巧集锦：https://graphics.stanford.edu/~seander/bithacks.html
OI 比赛的网站：https://oi-wiki.org/ 有空可以学习
