1. 问题背景与题目解析今天我们来拆解一道LeetCode上的困难题——1178. Number of Valid Words for Each Puzzle猜字谜。这道题出现在周赛430中属于位运算和哈希表结合的经典题型。题目大意是给定一组单词words和一个谜语集合puzzles要求找出每个puzzle对应的有效单词数量。有效单词的定义需要满足两个条件单词必须包含谜语的第一个字母单词的所有字母都必须在谜语中出现举个例子 words [aaaa,asas,able,ability,actt,actor,access] puzzles [aboveyz,abrodyz,abslute,absoryz,actresz,gaswxyz]对于第一个谜语aboveyz首字母是a有效单词有aaaa、asas、able、ability、actt、actor、access因为它们都包含a且所有字母都在aboveyz中。2. 暴力解法与复杂度分析2.1 直观思路的实现最直接的解法是对每个puzzle遍历所有words检查是否满足条件def findNumOfValidWords(words, puzzles): res [] for puzzle in puzzles: count 0 first_char puzzle[0] puzzle_set set(puzzle) for word in words: word_set set(word) if first_char in word_set and word_set.issubset(puzzle_set): count 1 res.append(count) return res2.2 时间复杂度分析假设words数量为Npuzzles数量为M平均单词长度为L预处理每个word为setO(N*L)对每个puzzle处理O(M*(NL NL)) O(MNL) 总时间复杂度为O(MNL)当N和M都很大时题目限制N,M≤10^5这种解法显然会超时。3. 位运算优化思路3.1 关键观察点这道题的核心在于如何高效判断word的所有字母都在puzzle中。位运算可以完美解决这个问题将每个单词和谜语转换为位掩码26位整数每位代表一个字母word的掩码与puzzle掩码的按位与操作结果如果等于word掩码说明word所有字母都在puzzle中同时需要检查word包含puzzle的第一个字母3.2 位掩码实现def get_mask(word): mask 0 for c in word: mask | 1 (ord(c) - ord(a)) return mask例如abc → 0b111 (第0,1,2位为1)aac → 同样0b111重复字母不影响3.3 优化后的算法步骤预处理所有words的位掩码并统计每种掩码出现的次数使用Counter对每个puzzle生成其位掩码和首字母位枚举puzzle掩码的所有子集必须包含首字母累加这些子集在words中出现的次数4. 子集枚举的巧妙处理4.1 子集生成算法对于puzzle的掩码puzzle_mask我们需要生成所有满足以下条件的子集subsetsubset包含puzzle的第一个字母即subset first_bit ! 0subset是puzzle_mask的子集即subset puzzle_mask subset可以采用位运算技巧高效枚举子集subset puzzle_mask while True: if subset first_bit: # 必须包含首字母 res count[subset] if subset 0: break subset (subset - 1) puzzle_mask4.2 复杂度分析优化后的算法预处理wordsO(N*L)处理每个puzzleO(M * K)其中K是puzzle的子集数量对于7字母的puzzle题目限制子集数量为2^7128实际由于必须包含首字母有效子集为64个 总时间复杂度为O(NL M64)可以高效处理最大规模输入。5. 完整实现与边界处理5.1 Python完整代码from collections import Counter class Solution: def findNumOfValidWords(self, words, puzzles): def get_mask(word): mask 0 for c in word: mask | 1 (ord(c) - ord(a)) return mask count Counter() for word in words: mask get_mask(word) count[mask] 1 res [] for puzzle in puzzles: puzzle_mask get_mask(puzzle) first_bit 1 (ord(puzzle[0]) - ord(a)) subset puzzle_mask total 0 while True: if subset first_bit: total count.get(subset, 0) if subset 0: break subset (subset - 1) puzzle_mask res.append(total) return res5.2 边界情况处理空单词或空谜语题目保证输入非空重复单词Counter会自动统计频率单个字母的word和puzzle位运算依然适用大小写问题题目说明所有字母都是小写6. 算法优化与变种思考6.1 进一步优化空间预处理时可以先过滤掉不可能匹配的word如包含puzzle首字母以外的字母对于特别长的words可以考虑分批次处理使用更高效的语言实现如C可以获得更好的性能6.2 相似题目推荐LeetCode 318. Maximum Product of Word LengthsLeetCode 416. Partition Equal Subset SumLeetCode 78. Subsets7. 实际应用场景这种位运算技巧在以下场景非常有用快速判断集合包含关系状态压缩如动态规划中表示状态权限系统中角色权限的快速检查基因序列匹配等生物信息学应用8. 解题心得与技巧遇到集合操作问题时位运算往往是优化方向子集枚举的位运算技巧需要熟练掌握(subset - 1) maskCounter的使用可以大大简化频率统计代码困难题通常需要多步优化先写出暴力解再思考优化方向注意题目中的特殊条件如必须包含首字母这往往是优化的关键提示位运算题目中预先计算好字母到位的映射表如{a:0, b:1,...}有时比每次都调用ord()更高效。这道题的难点在于如何想到用位运算表示字母集合以及如何处理必须包含首字母的条件。在实际面试中面试官可能会先让你写暴力解再引导你思考优化方向。掌握这类位运算技巧对解决LeetCode中等以上难度的题目非常有帮助。