# 1178. 猜字谜 ### 题目地址(1178. 猜字谜) ### 题目描述 ``` 外国友人仿照中国字谜设计了一个英文版猜字谜小游戏，请你来猜猜看吧。 字谜的迷面 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^5 4 <= words[i].length <= 50 1 <= puzzles.length <= 10^4 puzzles[i].length == 7 words[i][j], puzzles[i][j] 都是小写英文字母。 每个 puzzles[i] 所包含的字符都不重复。 ``` ### 前置知识 * 枚举子集 * 位运算 * 前缀树 ### 公司 * 暂无 ### 位运算 #### 思路 朴素的想法是模拟。即遍历 puzzles 和 words 的所有组合，并判断是否满足条件，如果满足则计数器+1，最后返回计数器的值。 暴力法代码： ```py class Solution: def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]: s_word = [set(word) for word in words] ans = [] for puzzle in puzzles: cnt = 0 for word in s_word: if puzzle[0] not in word: continue flag = False for c in word: if c not in puzzle: flag = True break if not flag: cnt += 1 ans.append(cnt) return ans ``` 由于这种做法需要遍历 puzzles 和 words 的所有组合，因此时间复杂不低于是 $O(m \* n)$，其中 m 和 n 分别为 words 和 puzzles 的长度。看下题目的约束条件： ``` 1 <= words.length <= 10^5 1 <= puzzles.length <= 10^4 ``` 可知道 m \* n 最大可以是 $10 ^ 9$ ，这显然是无法接受的。 > lucifer 小提示：小于等于 10 ^ 7 才可以哦 注意到题目的约束条件： ``` puzzles[i].length == 7 ``` 基本可以锁定为是**状态压缩**。力扣相关的题目很多，基本都是有一个约束条件的数据范围很小（比如 20 以内）。我们要做的通常就是**给这个小的变量做状态压缩**。 这道题的关键其实就是**单词 word 中的每一个字母都可以在谜面 puzzle 中找到**，所有的重复计算都是基于此产生的。这句话的含义其实就是**word 中字符组成的集合是 puzzle 中组成的集合的子集**。 基于上面两条重要信息，我们可以初步锁定算法为： * 用二进制表示 puzzle * 枚举 puzzle 的所有子集（二进制子集枚举） * 判断所有子集 j 是否在 words 中出现过。如果出现过，则将计数器累加出现的次数。这提示我们同样将 word 使用二进制进行存储。虽然 words\[i] 的长度范围比较大（\[4,50]），但我们关心的其实是**去重的子集**。注意到 words\[i] 的取值范围是小写字符，因此这个范围不大于 26，使用 int 存储完全够了。 枚举二进制子集是一个常见的操作，竞赛中也不时出现，大家可以阅读相关内容，具体原理不再展开。 #### 关键点 * 枚举子集算法 #### 代码 * 语言支持：Python3 Python3 Code: ```python class Solution: def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]: counts = collections.defaultdict(int) ans = [0] * len(puzzles) for word in words: bit = 0 # bit 是 word 的二进制表示 for c in word: bit |= 1 << ord(c) - ord("a") counts[bit] += 1 for i, puzzle in enumerate(puzzles): bit = 0 # bit 是 puzzle 的二进制表示 for c in puzzle: bit |= 1 << ord(c) - ord("a") j = bit # j 是 bit 的子集 # 倒序枚举 bit 的子集 j while j: # 单词 word 需要包含谜面的第一个字母 if 1 << ord(puzzle[0]) - ord("a") & j: ans[i] += counts[j] j = bit & (j - 1) return ans ``` **复杂度分析** 令 m 为 words 长度，w 为 word 的平均长度。n 为 puzzles 的长度，p 为 puzzle 的平均长度。 * 时间复杂度：$O(m*w + n*2^p)$ * 空间复杂度：$O(m)$ ### 字典树 #### 思路 看了官方的解答还提供了字典树的解法。于是我也用字典树实现了一遍。 之所以可以使用字典树求解是因为我们只关心： * word 是否是 puzzle 的子集 * 如果是，则关心 word 出现的次数 但由于类似：words: \["abc", "acb", "bac"] 等的存在，使得判断的时间大大增加，如果进行一次排序，此时 words 为：\["abc", "abc", "abc"]，而如果统计排序后相同 word 出现的次数，比如： ```py { "abc": 3 } ``` 这就可以仅判断一次而不是多次了，这就减少了判断。而这**对于我们求的答案来说是等价的**。除此之外，word 中一个字符出现几次对我们来说是一样的。比如 words: \["abc", "aaaaabbbc"] 可以看成是 \["abc", "abc"] 这**对于我们求的答案来说是等价的**。 因此我们可以将其进行一次**排序并去重**。同理，我们需要对 puzzle 进行排序并去重。而由于题目规定了 puzzle 本身不含重复字符，因此只对 puzzle 进行排序也是可以的。 这种做法同样需要枚举 puzzle 的子集。伪代码： ```py def get_subset(puzzle, pos): # ... get_subset(next_with_puzzle_pos , pos + 1) # 选 pos get_subset(next_without_puzzle_pos, pos + 1) # 不选 pos # ... ``` 由于第一个必选，因此上面的逻辑需要做一些微调，具体看下方代码区。 #### 关键点 * 字典树的基本用法 * 递归枚举子集 #### 代码 * 语言支持：Python3 Python3 Code: ```python class TrieNode: def __init__(self): self.count = 0 self.children = {} class Trie: def __init__(self): self.root = TrieNode() def insert(self, word): cur = self.root for c in word: if c not in cur.children: cur.children[c] = TrieNode() cur = cur.children[c] cur.count += 1 class Solution: def findNumOfValidWords(self, words: List[str], puzzles: List[str]) -> List[int]: trie = Trie() for word in words: trie.insert(sorted(set(word))) def get_count(first_letter, cur, i, puzzle): if i == len(puzzle): return cur.count if not cur: return 0 ans = 0 # 这个判断成立的条件是 puzzle 中不存在重复的字符， 这恰好就是题目的限制条件 if puzzle[i] != first_letter: ans += get_count(first_letter, cur, i + 1, puzzle) if puzzle[i] in cur.children: ans += get_count(first_letter, cur.children[puzzle[i]], i + 1, puzzle) return ans ``` **复杂度分析** 令 m 为 words 长度，w 为 word 的平均长度。n 为 puzzles 的长度，p 为 puzzle 的平均长度。 * 时间复杂度：$O(m*w + n*2^p)$ * 空间复杂度：$O(m\*w + p)$ > 此题解由 [力扣刷题插件](https://leetcode-pp.github.io/leetcode-cheat/?tab=solution-template) 自动生成。 力扣的小伙伴可以[关注我](https://leetcode-cn.com/u/fe-lucifer/)，这样就会第一时间收到我的动态啦\~ 以上就是本文的全部内容了。大家对此有何看法，欢迎给我留言，我有时间都会一一查看回答。更多算法套路可以访问我的 LeetCode 题解仓库： 。 目前已经 40K star 啦。大家也可以关注我的公众号《力扣加加》带你啃下算法这块硬骨头。 关注公众号力扣加加，努力用清晰直白的语言还原解题思路，并且有大量图解，手把手教你识别套路，高效刷题。 ![](https://p.ipic.vip/pviujz.jpg) --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://leetcode-solution-leetcode-pp.gitbook.io/leetcode-solution/hard/1178.number-of-valid-words-for-each-puzzle.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.