LeetCode 热题 100 49. 字母异位词分组

LeetCode 热题 100 | 49. 字母异位词分组

大家好，今天我们来解决一道经典的算法题——字母异位词分组。这道题在LeetCode上被标记为中等难度，要求我们将字母异位词组合在一起。下面我将详细讲解解题思路，并附上Python代码实现。

---

问题描述

给定一个字符串数组 strs，将其中所有字母异位词组合在一起。字母异位词是指由相同字母重新排列形成的单词。

示例：

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

---

解题思路

核心思想

1. 哈希表分组：

   • 使用哈希表（字典）来存储字母异位词的分组结果。
   • 将每个字符串排序后的结果作为哈希表的键，原始字符串作为值。

2. 排序作为键：

   • 由于字母异位词排序后的结果相同，可以将排序后的字符串作为哈希表的键。

3. 返回结果：

   • 遍历哈希表的值，将分组结果存入列表并返回。

---

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"]]

---

代码解析

1. 哈希表初始化：

   • 使用 defaultdict(list) 创建一个哈希表，键为排序后的字符串，值为原始字符串列表。

2. 遍历字符串数组：

   • 对每个字符串进行排序，并将排序后的字符串作为键，原始字符串添加到对应的列表中。

3. 返回结果：

   • 将哈希表的值转换为列表并返回。

---

复杂度分析

• 时间复杂度：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"]]

---

优化代码解析

1. 字符计数：

   • 使用长度为26的列表记录每个字符的出现次数。
   • 将字符计数转换为元组（因为列表不能作为哈希表的键）。

2. 时间复杂度：

   • 时间复杂度为 O(n * k)，其中 n 是字符串数组的长度，k 是字符串的最大长度。

---

总结

通过使用哈希表，我们可以高效地将字母异位词分组。排序法和字符计数法各有优劣，可以根据实际需求选择合适的方法。希望这篇题解对大家有所帮助，如果有任何问题，欢迎在评论区留言讨论！

关注我，获取更多算法题解和编程技巧！