1. 问题背景与核心概念解析今天我们来拆解LeetCode第916题单词子集Word Subsets。这是一道中等难度的字符串处理题目考察的是对字符频率统计和集合运算的理解能力。题目给定两个字符串数组words1和words2要求找出words1中所有满足特定条件的单词。关键术语定义单词子集对于单词b和a如果b中的每个字母在a中出现的次数都不超过a中该字母的出现次数则称b是a的子集通用单词如果words2中的每一个单词都是a的子集那么a就是通用单词举个例子如果a facebookb bookb在a中出现1次b中出现1次o在a中出现2次b中出现2次k在a中出现1次b中出现1次因此b是a的子集2. 暴力解法分析与优化思路2.1 直接暴力解法最直观的解法是对words1中的每个单词a检查words2中的每个单词b是否是a的子集。这种方法的时间复杂度是O(MNL)其中M是words1的长度N是words2的长度L是单词的平均长度。def wordSubsets(words1, words2): def is_subset(a, b): count_a collections.Counter(a) count_b collections.Counter(b) return all(count_a[ch] count_b[ch] for ch in count_b) result [] for word in words1: if all(is_subset(word, b) for b in words2): result.append(word) return result2.2 关键优化思路观察题目要求我们需要的是words1中满足words2所有单词都是其子集的单词。这里有一个重要性质如果一个单词a要包含words2中所有单词作为子集那么a必须包含所有这些单词的并集。具体来说我们可以先计算words2中所有单词的最大需求即对于每个字母取words2中所有单词对该字母需求的最大值然后只需要检查words1中的单词是否满足这个最大需求即可这样就将O(M*N)的时间复杂度降低到了O(MN)是一个显著的优化。3. 优化解法实现细节3.1 计算最大需求def get_max_requirements(words2): max_req collections.defaultdict(int) for word in words2: count collections.Counter(word) for ch in count: max_req[ch] max(max_req[ch], count[ch]) return max_req3.2 完整优化解法import collections def wordSubsets(words1, words2): # 计算words2的最大需求 max_req collections.defaultdict(int) for word in words2: count collections.Counter(word) for ch in count: max_req[ch] max(max_req[ch], count[ch]) # 检查words1中的单词是否满足最大需求 result [] for word in words1: count collections.Counter(word) if all(count[ch] max_req[ch] for ch in max_req): result.append(word) return result4. 复杂度分析与边界条件4.1 时间复杂度分析计算最大需求O(N*L)其中N是words2的长度L是单词平均长度检查words1O(M*K)其中M是words1的长度K是字母表大小最多26总时间复杂度O(NL MK)4.2 空间复杂度存储最大需求O(K)K是字母表大小存储结果最坏O(M)4.3 边界条件处理需要特别注意以下边界情况words2为空根据题意应该返回所有words1words1为空直接返回空列表包含大写字母题目说明只包含小写字母空字符串需要明确是否可能出现在输入中5. 实际编码中的技巧与陷阱5.1 实用技巧使用collections.Counter可以简化字符计数在Python中defaultdict(int)比普通字典更方便处理缺失键使用生成器表达式(all)可以节省内存5.2 常见错误忘记处理words2为空的情况在计算最大需求时错误地累加而不是取最大值错误理解子集定义必须是字符频率的子集而不仅仅是字符集的子集5.3 测试用例设计好的测试用例应该包括常规情况words2只有一个单词words2有重复单词words1中有满足和不满足的单词混合边界情况空列表、空字符串示例测试用例assert wordSubsets([facebook,google,leetcode], [e,o]) [facebook,google,leetcode] assert wordSubsets([amazon,apple,facebook,google,leetcode], [e,oo]) [facebook,google] assert wordSubsets([amazon,apple,facebook,google,leetcode], [lo,eo]) [google,leetcode] assert wordSubsets([aaa,aa,a], [a]) [aaa,aa,a] assert wordSubsets([], [a]) [] assert wordSubsets([a], []) [a]6. 算法扩展与变种思考这个问题可以延伸出一些有趣的变种如果改为至少k个words2中的单词是子集该如何解如果words2很大但有很多重复如何进一步优化如果允许一定容错比如允许缺少少量字符该如何修改算法如果单词很大比如是文档如何设计更高效的算法对于第一个变种可以考虑仍然计算words2中所有单词的字符频率然后对words1中的每个单词统计满足多少words2的子集最后筛选出满足数量≥k的单词这种变种的时间复杂度会增加到O(MNL)除非能找到更聪明的优化方法。