原文链接: https://leetcode-cn.com/problems/number-of-valid-words-for-each-puzzle
英文原文
puzzle string, a word is valid if both the following conditions are satisfied:
wordcontains the first letter ofpuzzle.- For each letter in
word, that letter is inpuzzle.- For example, if the puzzle is
"abcdefg", then valid words are"faced","cabbage", and"baggage", while - invalid words are
"beefed"(does not include'a') and"based"(includes's'which is not in the puzzle).
- For example, if the puzzle is
answer, where answer[i] is the number of words in the given word list words that is valid with respect to the puzzle puzzles[i].
Example 1:
Input: words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] Output: [1,1,3,2,4,0] Explanation: 1 valid word for "aboveyz" : "aaaa" 1 valid word for "abrodyz" : "aaaa" 3 valid words for "abslute" : "aaaa", "asas", "able" 2 valid words for "absoryz" : "aaaa", "asas" 4 valid words for "actresz" : "aaaa", "asas", "actt", "access" There are no valid words for "gaswxyz" cause none of the words in the list contains letter 'g'.
Example 2:
Input: words = ["apple","pleas","please"], puzzles = ["aelwxyz","aelpxyz","aelpsxy","saelpxy","xaelpsy"] Output: [0,1,3,2,0]
Constraints:
1 <= words.length <= 1054 <= words[i].length <= 501 <= puzzles.length <= 104puzzles[i].length == 7words[i]andpuzzles[i]consist of lowercase English letters.- Each
puzzles[i]does not contain repeated characters.
中文题目
外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。
字谜的迷面 puzzle 按字符串形式给出，如果一个单词 word 符合下面两个条件，那么它就可以算作谜底：
- 单词
word中包含谜面puzzle的第一个字母。 - 单词
word中的每一个字母都可以在谜面puzzle中找到。
例如，如果字谜的谜面是 "abcdefg"，那么可以作为谜底的单词有 "faced", "cabbage", 和 "baggage"；而 "beefed"（不含字母 "a"）以及 "based"（其中的 "s" 没有出现在谜面中）都不能作为谜底。
返回一个答案数组 answer，数组中的每个元素 answer[i] 是在给出的单词列表 words 中可以作为字谜迷面 puzzles[i] 所对应的谜底的单词数目。
示例：
输入： words = ["aaaa","asas","able","ability","actt","actor","access"], puzzles = ["aboveyz","abrodyz","abslute","absoryz","actresz","gaswxyz"] 输出：[1,1,3,2,4,0] 解释： 1 个单词可以作为 "aboveyz" 的谜底 : "aaaa" 1 个单词可以作为 "abrodyz" 的谜底 : "aaaa" 3 个单词可以作为 "abslute" 的谜底 : "aaaa", "asas", "able" 2 个单词可以作为 "absoryz" 的谜底 : "aaaa", "asas" 4 个单词可以作为 "actresz" 的谜底 : "aaaa", "asas", "actt", "access" 没有单词可以作为 "gaswxyz" 的谜底，因为列表中的单词都不含字母 'g'。
提示：
1 <= words.length <= 10^54 <= words[i].length <= 501 <= puzzles.length <= 10^4puzzles[i].length == 7words[i][j],puzzles[i][j]都是小写英文字母。- 每个
puzzles[i]所包含的字符都不重复。
通过代码
高赞题解
各位题友大家好！ 今天是 @负雪明烛 坚持日更的第 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 都做状态压缩，并用 hashmap 保存每个二进制数字出现的次数。
第二步：匹配
根据题目的两个条件，puzzle 的第一个字符必须跟 word 的第一个字符相同；word 中每一个字符都要在 puzzle 中找到，所以要找的是 word 状态压缩后的数字 和 puzzle[0] + subset(puzzle[1:N - 1]) 状态压缩后的数字相等。
很多题解都在讨论二进制表示下的 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]) 对应的二进制数字之后，累加 hashmap 中该二进制数字出现的次数，就是该 puzzle 对应的 word 有多少。
代码
Python 代码如下，直接用了 78 题的求 subset 代码。
class Solution:
def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]:
freq = collections.Counter()
for word in words:
mask = 0
for c in word:
mask |= 1 << (ord(c) - ord('a'))
freq[mask] += 1
res = []
for puzzle in puzzles:
total = 0
for perm in self.subsets(puzzle[1:]):
mask = 1 << (ord(puzzle[0]) - ord('a'))
for c in perm:
mask |= 1 << (ord(c) - ord('a'))
total += freq[mask]
res.append(total)
return res
def subsets(self, words: List[int]) -> List[List[int]]:
res = [""]
for i in words:
res = res + [i + word for word in res]
return res- 时间复杂度：$O(M + N)$。
- 空间复杂度：$O(M)$。
刷题心得
不畏浮云遮望眼，透过现象看本质。
OK，以上就是 @负雪明烛 写的今天题解的全部内容了，如果你觉得有帮助的话，求赞、求关注、求收藏。如果有疑问的话，请在下面评论，我会及时解答。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。
欢迎关注我的公众号：每日算法题
祝大家牛年大吉！AC 多多，Offer 多多！我们明天再见！
统计信息
| 通过次数 | 提交次数 | AC比率 |
|---|---|---|
| 18800 | 40655 | 46.2% |
提交历史
| 提交时间 | 提交结果 | 执行时间 | 内存消耗 | 语言 |
|---|
