好的，我们这次来详细讲解 LeetCode 第 49 题「字母异位词分组」。

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. 题意理解与思路分析

关键点：

• 字母异位词：两个字符串包含的字符种类和数量完全相同，只是排列顺序不同。
• 目标：将字母异位词分到同一组。

思路：
我们需要一个方法，让属于同一组的字符串映射到同一个“键”，然后把这些字符串放到该键对应的值（列表）中。

常见方法：

1. 排序法：将每个字符串排序，排序后的字符串作为键。
   • 例如 "eat"、"tea"、"ate" 排序后都是 "aet"。
2. 计数法：统计每个字符串中每个字符出现的次数，将计数数组（或序列化后的字符串）作为键。
   • 例如 "abb" 可以表示为 #1#2#0...#0（a 出现 1 次，b 出现 2 次，其余字母 0 次）。

3. 方法一：排序作为键（详细步骤）

步骤：

1. 创建一个哈希表 map，键是排序后的字符串，值是原字符串列表。
2. 遍历 strs 中的每个字符串 s：
   • 将 s 转换为字符数组，排序，再转回字符串得到 key。
   • 如果 key 不在 map 中，就创建一个新列表，放入 (key, [s])。
   • 如果 key 已存在，就把 s 追加到对应的列表中。
3. 最后返回 map 中所有值的集合。

复杂度分析：

• 设 n 是字符串个数，k 是字符串的最大长度。
• 排序每个字符串：O(k log k)。
• 总复杂度：O(n * k log k)。
• 空间复杂度：O(n * k)（存储所有字符串）。

代码实现（Python）：

import collections

def groupAnagrams(strs):
    ans = collections.defaultdict(list)
    for s in strs:
        key = ''.join(sorted(s))
        ans[key].append(s)
    return list(ans.values())

举例说明：

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

处理过程：
"eat" -> sorted -> "aet" -> map["aet"] = ["eat"]
"tea" -> sorted -> "aet" -> map["aet"] = ["eat", "tea"]
"tan" -> sorted -> "ant" -> map["ant"] = ["tan"]
"ate" -> sorted -> "aet" -> map["aet"] = ["eat", "tea", "ate"]
"nat" -> sorted -> "ant" -> map["ant"] = ["tan", "nat"]
"bat" -> sorted -> "abt" -> map["abt"] = ["bat"]

结果： [["eat","tea","ate"],["tan","nat"],["bat"]]
（顺序可能不同）

4. 方法二：计数作为键（详细步骤）

思路：

• 由于字符串只包含小写字母，我们可以用一个长度为 26 的数组统计每个字符出现的次数。
• 然后将该数组转换成一个形如 #1#2#0...#0 的字符串作为键（'#' 分隔是为了避免计数位数不同导致的混淆，例如 12 和 1 与 2 的区别）。

步骤：

1. 创建一个哈希表 map。
2. 遍历 strs 中的每个字符串 s：
   • 创建一个长度为 26 的计数数组，初始为 0。
   • 遍历 s 的每个字符，对应计数加 1。
   • 将计数数组转换成字符串键（例如用 # 连接计数）。
   • 将 s 加入该键对应的列表。
3. 返回所有列表。

复杂度分析：

• 时间复杂度：O(n * k)，其中 k 为字符串最大长度。
• 空间复杂度：O(n * k)。

代码实现（Python）：

import collections

def groupAnagrams(strs):
    ans = collections.defaultdict(list)
    for s in strs:
        count = [0] * 26
        for c in s:
            count[ord(c) - ord('a')] += 1
        key = tuple(count)  # 列表不能做键，转成元组
        ans[key].append(s)
    return list(ans.values())

举例说明：

"abb" 的计数数组：
a -> 1, b -> 2, 其余 0
count = [1, 2, 0, 0, ...]
key = (1, 2, 0, 0, ...) （元组形式）

"bab" 计数数组一样，所以 key 相同，分到同一组。

5. 两种方法对比

一般情况 k 不会太大，排序法更直观且实现简单，所以常用。

6. 总结

• 核心：如何为字母异位词设计相同的哈希键。
• 排序法直观易懂，写起来快。
• 计数法理论更优，适合字符串较长且字符种类有限的情况。
• 最终返回的是分组后的列表集合，不要求顺序。

这样循序渐进地讲解，你是否完全理解了这道题的解法？如果有任何疑问，我可以进一步解释。