好的，我们这次来详细讲解 LeetCode 第 49 题：字母异位词分组（Group Anagrams）。

1. 题目描述

题目链接：https://leetcode.com/problems/group-anagrams/

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 1 <= strs.length <= 10^4
• 0 <= strs[i].length <= 100
• strs[i] 仅包含小写英文字母

2. 题意理解

字母异位词（anagram）的定义是：两个字符串的字符种类和数量完全相同，只是排列顺序不同。
例如 "eat"、"tea"、"ate" 互为字母异位词。

我们要做的是：将输入数组中所有的字母异位词分到同一组，最后返回一个分组列表。

关键点：如何判断两个字符串是字母异位词？

3. 判断字母异位词的几种方法

方法 1：排序

• 对每个字符串按字符排序，排序后的字符串作为“标准键”。
• 互为字母异位词的字符串排序后一定相同。

例如：

• "eat" → "aet"
• "tea" → "aet"
• "ate" → "aet"

这样它们就有相同的键。

方法 2：字符计数

• 统计每个字符串中每个字符的出现次数，用一个长度 26 的数组（对应 26 个小写字母）表示。
• 把这个计数数组转换成唯一字符串作为键（例如用 # 分隔数字，或者直接转成元组等）。

例如：

• "eat" → [1,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0]
• 可以表示为 "1#0#0#...1..." 或 (1,0,0,...,1,...)。

4. 分组思路

我们可以用一个哈希表（字典），键是上面得到的“标准键”，值是原字符串的列表。

步骤：

1. 创建一个空字典 groups。
2. 遍历 strs 中的每个字符串 s：
   • 计算 s 的标准键（排序或计数方式）。
   • 如果该键不在字典中，则创建一个新列表 [s] 存入字典。
   • 如果该键已存在，则将 s 追加到对应的列表中。
3. 遍历结束后，字典中每个键对应的值就是一个分组，将它们收集成列表返回。

5. 方法 1 详细步骤（排序法）

时间复杂度分析：

• 设字符串数组长度为 n，字符串平均长度为 k。
• 排序一个字符串的时间是 O(k log k)。
• 对每个字符串排序，总时间 O(n * k log k)。
• 哈希表插入 O(1)（平均）。

空间复杂度：

• 哈希表存储所有字符串，O(n * k)。

代码实现思路：

def groupAnagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    
    for s in strs:
        # 排序得到标准键
        key = ''.join(sorted(s))
        groups[key].append(s)
    
    return list(groups.values())

6. 方法 2 详细步骤（计数法）

时间复杂度分析：

• 统计每个字符串的字符频次 O(k)。
• 总时间 O(n * k)。
• 比排序法在 k 较大时可能更快（因为 k log k 比 k 大）。

空间复杂度：

• 同排序法，O(n * k)。

代码实现思路：

def groupAnagrams(strs):
    from collections import defaultdict
    groups = defaultdict(list)
    
    for s in strs:
        count = [0] * 26
        for ch in s:
            count[ord(ch) - ord('a')] += 1
        # 将计数数组转成元组作为键（因为字典键需要可哈希）
        key = tuple(count)
        groups[key].append(s)
    
    return list(groups.values())

7. 对比两种方法

• 排序法：实现简单，代码短，在字符串长度 k 较小时非常高效。
• 计数法：当 k 很大时，O(nk) 优于 O(nk log k)，并且不依赖排序。

在 LeetCode 上，两种方法通常都能通过，但计数法理论更优，尤其适用于字符集有限的情况。

8. 举例演示

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

用排序法：

1. "eat" → 排序 "aet"，组 ["eat"]
2. "tea" → 排序 "aet"，组 ["eat","tea"]
3. "tan" → 排序 "ant"，新组 ["tan"]
4. "ate" → 排序 "aet"，组 ["eat","tea","ate"]
5. "nat" → 排序 "ant"，组 ["tan","nat"]
6. "bat" → 排序 "abt"，新组 ["bat"]

最终分组：

[["eat","tea","ate"], ["tan","nat"], ["bat"]]

（顺序可能不同）

9. 边界情况

• 空字符串 [""] → 键是空字符串 ""，分组 [[""]]。
• 单个字符 ["a"] → 键 "a"，分组 [["a"]]。

10. 总结

这道题的核心是：

1. 理解字母异位词的定义。
2. 选择一个合适的“标准化”方法将异位词映射到同一键。
3. 使用哈希表分组。

这样就能在 O(nk) 或 O(nk log k) 时间内高效解决问题。