网站建设diy,勒流网站制作,软文推广文案,app下载的视频为什么手机找不到LeetCode 热题 100 | 49. 字母异位词分组
大家好#xff0c;今天我们来解决一道经典的算法题——字母异位词分组。这道题在LeetCode上被标记为中等难度#xff0c;要求我们将字母异位词组合在一起。下面我将详细讲解解题思路#xff0c;并附上Python代码实现。 问题描述
给…LeetCode 热题 100 | 49. 字母异位词分组
大家好今天我们来解决一道经典的算法题——字母异位词分组。这道题在LeetCode上被标记为中等难度要求我们将字母异位词组合在一起。下面我将详细讲解解题思路并附上Python代码实现。 问题描述
给定一个字符串数组 strs将其中所有字母异位词组合在一起。字母异位词是指由相同字母重新排列形成的单词。
示例
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]解题思路
核心思想 哈希表分组 使用哈希表字典来存储字母异位词的分组结果。将每个字符串排序后的结果作为哈希表的键原始字符串作为值。 排序作为键 由于字母异位词排序后的结果相同可以将排序后的字符串作为哈希表的键。 返回结果 遍历哈希表的值将分组结果存入列表并返回。 Python代码实现
def groupAnagrams(strs):from collections import defaultdict# 使用 defaultdict 初始化哈希表anagrams defaultdict(list)# 遍历字符串数组for s in strs:# 将字符串排序后作为键sorted_s .join(sorted(s))# 将原始字符串添加到对应的分组中anagrams[sorted_s].append(s)# 返回分组结果return list(anagrams.values())# 测试示例
strs1 [eat, tea, tan, ate, nat, bat]
strs2 []
strs3 [a]print(groupAnagrams(strs1)) # 输出: [[bat],[nat,tan],[ate,eat,tea]]
print(groupAnagrams(strs2)) # 输出: [[]]
print(groupAnagrams(strs3)) # 输出: [[a]]代码解析 哈希表初始化 使用 defaultdict(list) 创建一个哈希表键为排序后的字符串值为原始字符串列表。 遍历字符串数组 对每个字符串进行排序并将排序后的字符串作为键原始字符串添加到对应的列表中。 返回结果 将哈希表的值转换为列表并返回。 复杂度分析
时间复杂度O(n * k log k)其中 n 是字符串数组的长度k 是字符串的最大长度。排序每个字符串的时间复杂度为 O(k log k)。空间复杂度O(n * k)用于存储哈希表。 示例运行
示例1
输入: strs [eat, tea, tan, ate, nat, bat]
输出: [[bat],[nat,tan],[ate,eat,tea]]示例2
输入: strs []
输出: [[]]示例3
输入: strs [a]
输出: [[a]]优化思路
如果字符串长度较短可以使用字符计数作为哈希表的键进一步优化时间复杂度。
优化代码
def groupAnagrams_optimized(strs):from collections import defaultdictanagrams defaultdict(list)for s in strs:# 使用字符计数作为键count [0] * 26for char in s:count[ord(char) - ord(a)] 1# 将字符计数转换为元组因为列表不能作为哈希表的键anagrams[tuple(count)].append(s)return list(anagrams.values())# 测试示例
strs1 [eat, tea, tan, ate, nat, bat]
strs2 []
strs3 [a]print(groupAnagrams_optimized(strs1)) # 输出: [[bat],[nat,tan],[ate,eat,tea]]
print(groupAnagrams_optimized(strs2)) # 输出: [[]]
print(groupAnagrams_optimized(strs3)) # 输出: [[a]]优化代码解析 字符计数 使用长度为26的列表记录每个字符的出现次数。将字符计数转换为元组因为列表不能作为哈希表的键。 时间复杂度 时间复杂度为 O(n * k)其中 n 是字符串数组的长度k 是字符串的最大长度。 总结
通过使用哈希表我们可以高效地将字母异位词分组。排序法和字符计数法各有优劣可以根据实际需求选择合适的方法。希望这篇题解对大家有所帮助如果有任何问题欢迎在评论区留言讨论
关注我获取更多算法题解和编程技巧
