字母频率统计在字符串子集匹配中的应用

1. 问题解析与核心思路第一次看到这个题目时我花了10分钟才真正理解题意。题目要求我们找出words1中所有满足条件的单词a对于words2中的每一个单词bb都是a的子集。这里的子集不是指字符串的子串而是指字母组成的集合关系。举个例子words1 [amazon,apple,facebook,google]words2 [e,o] 结果应该是[facebook,google]因为facebook包含所有e和o的字母google也是同理而amazon缺少eapple缺少o1.1 关键突破点经过反复思考我意识到可以先将words2合并成一个超级单词统计words2中所有单词的字母频率取每个字母的最大频率这样得到的频率表就是我们需要在words1中匹配的目标然后检查words1中的每个单词是否包含这个超级单词的所有字母频率足够比如words2 [ee,oo]合并后就是{e:2, o:2}任何包含至少2个e和2个o的单词都满足条件。2. 详细解法与代码实现2.1 统计字母频率的辅助函数首先我们需要一个辅助函数来统计单词的字母频率def count_letters(word): freq [0] * 26 for c in word: freq[ord(c) - ord(a)] 1 return freq这个函数返回一个长度为26的列表对应a-z的计数。比如apple会返回 [1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]2.2 构建超级单词接下来是构建words2的合并频率表def build_super_word(words2): super_freq [0] * 26 for word in words2: curr_freq count_letters(word) for i in range(26): super_freq[i] max(super_freq[i], curr_freq[i]) return super_freq这个函数遍历words2中的每个单词对每个字母取最大频率。比如words2[ee,oo]会返回 [0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]2.3 检查单词是否满足条件然后我们需要检查words1中的单词是否包含超级单词的所有字母def is_subset(word_freq, super_freq): for i in range(26): if word_freq[i] super_freq[i]: return False return True这个辅助函数比较两个频率表如果word_freq中每个字母的计数都大于等于super_freq则返回True。2.4 完整解法代码将以上部分组合起来class Solution: def wordSubsets(self, words1: List[str], words2: List[str]) - List[str]: super_freq self.build_super_word(words2) result [] for word in words1: word_freq self.count_letters(word) if self.is_subset(word_freq, super_freq): result.append(word) return result def build_super_word(self, words2): super_freq [0] * 26 for word in words2: curr_freq self.count_letters(word) for i in range(26): super_freq[i] max(super_freq[i], curr_freq[i]) return super_freq def count_letters(self, word): freq [0] * 26 for c in word: freq[ord(c) - ord(a)] 1 return freq def is_subset(self, word_freq, super_freq): for i in range(26): if word_freq[i] super_freq[i]: return False return True3. 复杂度分析与优化3.1 时间复杂度让我们分析下这个算法的时间复杂度构建超级单词O(N * L)其中N是words2的长度L是words2中最长单词的长度检查words1中的每个单词O(M * K)其中M是words1的长度K是words1中最长单词的长度 总时间复杂度是O(NL MK)3.2 空间复杂度空间复杂度主要是存储频率表超级单词频率表固定26个整数临时频率表每次处理单词时创建也是26个整数 所以空间复杂度是O(1)常数空间3.3 可能的优化在实际编码中我们可以做一些小优化提前计算超级单词的总字母数如果某个单词的总字母数小于这个值可以直接跳过对于words1中的单词可以预处理它们的频率表避免重复计算使用位运算来加速比较虽然对于这个问题可能提升不大4. 常见错误与调试技巧4.1 常见错误误解题意把子集理解为子串或子序列解决方法仔细阅读题目说明用示例验证理解没有正确处理重复字母比如words2[ee,oo]需要确保单词包含至少2个e和2个o解决方法使用频率统计而非集合性能问题对于大输入可能超时解决方法确保算法复杂度合理避免嵌套循环4.2 调试技巧打印中间结果print(Super freq:, super_freq) print(Checking word:, word, freq:, word_freq)使用小测试用例先测试简单情况如words2只有一个单词然后测试words2有多个单词的情况边界条件测试空输入包含重复单词大小写问题虽然题目说明是小写5. 实际应用场景这个问题虽然看起来是纯算法题但其实有实际应用背景搜索引擎的查询扩展当用户输入多个关键词时找出包含所有关键词的文档类似words2代表用户查询words1代表文档集合拼写检查检查一个单词是否包含另一个单词的所有字母可用于单词游戏或教育软件数据过滤在大型数据集中快速筛选满足多个条件的记录每个条件对应words2中的一个单词6. 类似题目推荐如果你觉得这个问题有趣可以尝试以下类似题目Find All Anagrams in a String找字符串中所有字母异位词同样使用字母频率统计技巧Partition Labels划分字母区间需要统计字母出现位置Permutation in String判断一个字符串的排列是否存在于另一个字符串中滑动窗口与频率统计的结合Group Anagrams将字母异位词分组使用字母频率作为哈希键7. 个人解题心得这道题教会了我几个重要的编程技巧问题转化的重要性将复杂的条件判断转化为简单的频率比较这是算法设计中常用的问题归约思想预处理的价值提前计算并存储中间结果超级单词避免在主要逻辑中重复计算空间换时间的权衡使用固定大小的频率表虽然占用了一些空间但大大提高了时间效率在实际面试中这类字符串处理题目非常常见。掌握字母频率统计这一基础技巧可以解决一大类相关问题。建议多练习类似的题目培养对这类问题的敏感度。