LeetCode 49. 字母异位词分组：Python 排序哈希表解法详解

1. 问题描述

给你一个字符串数组strs，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1：

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

示例 2：

输入: strs = [""] 输出: [[""]]

示例 3：

输入: strs = ["a"] 输出: [["a"]]

2. 核心思路分析

字母异位词的核心特征是：排序后字符串相同。例如 "eat"、"tea"、"ate" 排序后都是 "aet"。

因此，我们可以将每个字符串排序后的结果作为哈希表的键，将原始字符串添加到该键对应的列表中。这样，所有字母异位词就会被自动分组到同一个键下。

3. Python 代码实现

以下是完整的 Python 解法：

from typing import List import collections class Solution: def groupAnagrams(self, strs: List[str]) -> List[List[str]]: hashmap = collections.defaultdict(list) for st in strs: # 先用 sorted 函数对字符串进行排序 key1 = sorted(st) # 再用 join 函数拼接字符串 key = ''.join(key1) hashmap[key].append(st) return list(hashmap.values())

4. 代码逐行解析

• 第 4 行：使用collections.defaultdict(list)创建一个默认值为空列表的哈希表。这样在访问不存在的键时，会自动创建一个空列表，避免 KeyError。
• 第 5-9 行：遍历输入数组中的每个字符串。
  • sorted(st)：将字符串转换为字符列表并排序，返回排序后的字符列表。
  • ''.join(key1)：将排序后的字符列表重新拼接成字符串，作为哈希表的键。
  • hashmap[key].append(st)：将原始字符串添加到该键对应的列表中。
• 第 10 行：返回哈希表中所有值的列表，即分组后的结果。

5. 复杂度分析

• 时间复杂度：O(nk log k)，其中 n 是字符串数组的长度，k 是字符串的最大长度。对每个字符串排序需要 O(k log k) 时间。
• 空间复杂度：O(nk)，哈希表需要存储所有字符串。

6. 总结

字母异位词分组是哈希表应用的经典题目。通过将排序后的字符串作为键，可以巧妙地利用哈希表的特性实现高效分组。掌握这种思路对于解决类似的字符串分组问题非常有帮助。