各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 33 天。今天力扣上的每日一题是「1178. 猜字谜」。

解题思路

本文的两个重点：

  • 把每个字符串用二进制数字表示（状态压缩）
  • 寻找所有子集（subset）

大家好，今天的题虽然是 Hard，但是大家不要怕，本题解把难度降为了 Medium，肯定让你看懂。

首先让所有 words 和 puzzle 两两匹配肯定是不行的，时间复杂度到了 $O(M * N) = 10 ^ 9$，会超时。

一个简单的思路是，对于每个 puzzle 没有必要遍历所以 words，只用找符合条件的 words 出现了多少次就行了。这就是很多题解的思路：状态压缩。

题目给出了两个条件：

  • 单词 word 中包含谜面 puzzle 的第一个字母。
  • 单词 word 中的每一个字母都可以在谜面 puzzle 中找到。

第一步，状态压缩

注意题目的第二个条件只要求能找到（出现一次即可），对出现次数没要求。为了解决这个问题，我们可以使用二进制数字来表每个 word 和 puzzle，该二进制数字就是 word 和 puzzle 的特征。这道题只包含26个小写字母，可以压缩到一个 int 中。int 中的每一位取0和1表示字符是否出现过。比如 “aabb” 可以用 11 表示，”accc” 可以用 101 表示。

可以看出不同的单词可能映射成同一个数字，比如 “aabbb” 和 “ab” 都映射成了 11。这就是状态压缩。

把每个word都做状态压缩，用freq保存每个二进制数字出现的次数。

第二步，匹配

我们要用puzzle[0] + subset(puzzle[1:N - 1]) 对应的二进制数字去跟 word 的二进制做匹配。

很多题解都在讨论二进制表示下的 subset 怎么求，我觉得都不好理解，直接做一下「78. 子集」不就得了？暴力求出每个puzzle[1:N - 1]的全排列，然后计算每个排列下puzzle[0] + subset(puzzle[1:N - 1])对应的二进制数字。

题目说了 puzzle 的长度为 7 位，subset(puzzle[1:N - 1]) 的是时间复杂度为 $O(2 ^ N)$ = $2 ^ 6 = 64$ 次计算，比较快。

求出puzzle[0] + subset(puzzle[1:N - 1]) 对应的二进制数字之后，累加 freq 中出现的次数，就是该puzzle对应的word有多少。

代码

Python 代码如下，直接用了 78 题的求 subset 代码。

  1. class Solution:
  2.     def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
  3.         freq = collections.Counter()
  4.         for word in words:
  5.             mask = 0
  6.             for c in word:
  7.                 mask |= 1 << (ord(c) - ord('a'))
  8.             freq[mask] += 1
  9.         res = []
  10.         for puzzle in puzzles:
  11.             total = 0
  12.             for perm in self.subsets(puzzle[1:]):
  13.                 mask = 1 << (ord(puzzle[0]) - ord('a'))
  14.                 for c in perm:
  15.                     mask |= 1 << (ord(c) - ord('a'))
  16.                 total += freq[mask]
  17.             res.append(total)
  18.         return res
  20.     def subsets(self, words: List[int]) -> List[List[int]]:
  21.         res = [""]
  22.         for i in words:
  23.             res = res + [i + word for word in res]
  24.         return res
  • 时间复杂度：O(M + N)。
  • 空间复杂度：O(M)。

刷题心得

不畏浮云遮望眼，透过现象看本质。

OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。

关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。

祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！