企业官网建设流程全解析

1. 问题背景与题目解析

今天我们来拆解一道LeetCode上的困难题——1178. Number of Valid Words for Each Puzzle（猜字谜）。这道题出现在周赛430中，属于位运算和哈希表结合的经典题型。题目大意是给定一组单词words和一个谜语集合puzzles，要求找出每个puzzle对应的有效单词数量。

有效单词的定义需要满足两个条件：

1. 单词必须包含谜语的第一个字母
2. 单词的所有字母都必须在谜语中出现

举个例子： 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 res

2.2 时间复杂度分析

假设words数量为N，puzzles数量为M，平均单词长度为L：

• 预处理每个word为set：O(N*L)
• 对每个puzzle处理：O(M*(NL + NL)) = O(MNL) 总时间复杂度为O(MNL)，当N和M都很大时（题目限制N,M≤10^5），这种解法显然会超时。

3. 位运算优化思路

3.1 关键观察点

这道题的核心在于如何高效判断"word的所有字母都在puzzle中"。位运算可以完美解决这个问题：

1. 将每个单词和谜语转换为位掩码（26位整数，每位代表一个字母）
2. word的掩码与puzzle掩码的按位与操作结果如果等于word掩码，说明word所有字母都在puzzle中
3. 同时需要检查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 优化后的算法步骤

1. 预处理所有words的位掩码，并统计每种掩码出现的次数（使用Counter）
2. 对每个puzzle：
   • 生成其位掩码和首字母位
   • 枚举puzzle掩码的所有子集（必须包含首字母）
   • 累加这些子集在words中出现的次数

4. 子集枚举的巧妙处理

4.1 子集生成算法

对于puzzle的掩码puzzle_mask，我们需要生成所有满足以下条件的子集subset：

1. subset包含puzzle的第一个字母（即subset & first_bit != 0）
2. subset是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_mask

4.2 复杂度分析

优化后的算法：

1. 预处理words：O(N*L)
2. 处理每个puzzle：O(M * K)，其中K是puzzle的子集数量
   • 对于7字母的puzzle（题目限制），子集数量为2^7=128
   • 实际由于必须包含首字母，有效子集为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 res

5.2 边界情况处理

1. 空单词或空谜语：题目保证输入非空
2. 重复单词：Counter会自动统计频率
3. 单个字母的word和puzzle：位运算依然适用
4. 大小写问题：题目说明所有字母都是小写

6. 算法优化与变种思考

6.1 进一步优化空间

1. 预处理时可以先过滤掉不可能匹配的word（如包含puzzle首字母以外的字母）
2. 对于特别长的words，可以考虑分批次处理
3. 使用更高效的语言实现（如C++）可以获得更好的性能

6.2 相似题目推荐

1. LeetCode 318. Maximum Product of Word Lengths
2. LeetCode 416. Partition Equal Subset Sum
3. LeetCode 78. Subsets

7. 实际应用场景

这种位运算技巧在以下场景非常有用：

1. 快速判断集合包含关系
2. 状态压缩（如动态规划中表示状态）
3. 权限系统中角色权限的快速检查
4. 基因序列匹配等生物信息学应用

8. 解题心得与技巧

1. 遇到集合操作问题时，位运算往往是优化方向
2. 子集枚举的位运算技巧需要熟练掌握：(subset - 1) & mask
3. Counter的使用可以大大简化频率统计代码
4. 困难题通常需要多步优化，先写出暴力解再思考优化方向
5. 注意题目中的特殊条件（如必须包含首字母），这往往是优化的关键

提示：位运算题目中，预先计算好字母到位的映射表（如{'a':0, 'b':1,...}）有时比每次都调用ord()更高效。

这道题的难点在于如何想到用位运算表示字母集合，以及如何处理必须包含首字母的条件。在实际面试中，面试官可能会先让你写暴力解，再引导你思考优化方向。掌握这类位运算技巧对解决LeetCode中等以上难度的题目非常有帮助。