1178. 猜字谜

发表于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 4 分钟

这是今天的打卡题，我打开一看标签是困难，心里咯噔一声，觉得完蛋，今天我肯定做不出来了。事实也确实如此。

这道题的意思是，给出一个 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
34
class 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
30
class 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/ 有空可以学习