49.字母异位词分组

引导思路

第一步：寻找“字母异位词”的本质特征

题目中说，"ate", "eat", "tea" 是字母异位词，因为它们可以重新排列形成彼此。
引导问题 1：如果不考虑它们原本的拼写顺序，这三个词有什么完全一样的地方？
提示：想象如果你把它们里面的字母按照 A-Z 的顺序重新排一下，会变成什么样？

第二步：设计分组策略

现在我们知道，只要能找到某种“统一的标准”，把每个字符串转换一下，转换后长得一样的，就说明是同一组异位词。
引导问题 2：如果我们用一个字典（哈希表，dict）来保存结果，这个字典的 Key（键） 应该是什么？Value（值） 应该是什么？

提示：Python 里的字典，Key 必须是不可变的类型（如字符串、元组）。

第三步：构思算法流程

结合上面的思路，你能理顺整个代码的执行逻辑吗？
引导问题 3：如果遍历输入列表 strs，对每一个字符串 s，我们需要做哪几步操作？

1. 将 s 转换成我们刚才说的“统一标准”。
2. 去字典里查这个标准存不存在。
3. 如果不存在，该怎么办？
4. 如果存在，该怎么办？
5. 遍历结束后，怎么得到最终结果？

第四步：进阶与优化（可选）

按照上面的思路写出来，代码已经可以通过了。但我们可以再深入一点：
引导问题 4：第一步中“排序”操作，时间复杂度是 (O(k \log k))（(k) 是字符串长度）。如果不排序，我们能不能用统计字母频次的方法来代替？怎么把统计结果变成字典的 Key？

📝 给你的“骨架”代码（填空版）

你可以先不看具体实现，尝试自己填补下面代码中的 ??? 部分：

def groupAnagrams(strs):
    # 1. 准备一个字典存放结果
    anagram_map = ??? 
    
    for s in strs:
        # 2. 生成当前字符串的“统一标准” (Key)
        # 方式一：排序法。比如用 sorted(s) 会得到列表，怎么变成字符串？
        key = ??? 
        
        # 3. 存入字典
        if key not in anagram_map:
            anagram_map[key] = ???  # 如果是新分组，应该初始化为什么？
        anagram_map[key].append(???) # 把什么加进这个组里？
        
    # 4. 返回结果
    return ??? # 我们需要字典的值还是键？

详细过程

排序法

这道题最经典、最核心的解法——排序法。

把 "ate" 变成 ["a", "t", "e"]，再排序变成 ["a", "e", "t"]，那么 "eat" 和 "tea" 经过同样的操作后，也都会得到一模一样的 ["a", "e", "t"]。这就相当于给它们打上了同一个"标签"。

不过，在 Python 的代码实现中，这里有一个非常关键的"坑"，直接关系到我们能不能进入第二步：

遇到的小问题：字典的 Key

在 Python 里，列表（list）是不可哈希（unhashable）的。也就是说，如果你尝试把一个列表 ["a", "e", "t"] 直接当作字典的 Key，Python 会直接报错：TypeError: unhashable type: 'list'。

引导问题：我们怎么把列表 ["a", "e", "t"] 变成一个字符串（比如变成 "aet"），以便它能够作为字典的 Key 呢？

提示：Python 里有一个非常强大的字符串方法，可以把列表里的元素拼接到一起。

你可以先在本地或者脑海中试着写一下，如何用代码把 "ate" 变成 "aet" 这个字符串？

join()方法

split() 是把一个字符串拆分成列表（比如 "a,e,t".split(",") 变成 ["a", "e", "t"]）。

我们需要的是把列表拼成一个字符串，在 Python 中，用来拼接字符串的"神器"是 join() 方法。

用法是这样的：

# 假设我们先对字符串进行了排序，得到一个列表
chars = sorted("ate")  # 得到 ['a', 'e', 't']

# 使用 join 把它拼成一个字符串
key = "".join(chars)   # 得到 "aet"

这里的 "" 表示用"空字符"把它们连接起来。

结合你刚才的思路，我们可以用一行代码就搞定这个 Key：

key = "".join(sorted("ate"))  # 得到 "aet"

你可以在 Python 里试一下这行代码，看看结果是不是你想要的。

进入第二步：设计字典

现在我们有了统一的标签（比如 "aet"），接下来就要用到字典来分类了。

引导问题：如果我们定义一个字典 anagram_map = {}，

• Key（键）：就是我们刚才算出来的 key（比如 "aet"）。
• Value（值）：应该是什么类型的数据呢？是字符串、整数，还是列表？

提示：题目要求返回一个包含多个分组的列表，例如 [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]。字典的 Value 应该长什么样，才能装下这几个长得像的单词？

键就是按字母表顺序完成的"aet"，值就是给的字符串中，重排序之后符合"aet"的数组

• Key："aet" （排序后的字符串）
• Value：["ate", "eat", "tea"] （包含所有异位词的列表）

比如遍历完示例后，我们的字典大概长这样：

{
    "aet": ["ate", "eat", "tea"],
    "ant": ["nat", "tan"],
    "abt": ["bat"]
}

进入第三步：串联算法流程

现在我们有了字典的结构（字典 = {排序后的字符串: [原字符串列表]}），接下来就是遍历输入的字符串数组 strs，把数据填进去。

引导问题：如果我们正在遍历，拿到一个单词 s（比如 "eat"）：

1. 算出它的 Key（"aet"）。
2. 如果这个 Key 已经在字典里了，我们要把 "eat" 怎么处理？
3. 如果这个 Key 还不存在，我们要怎么初始化这个 Value 的列表，并把它放进去？

提示：Python 字典有一个非常方便的 dict.setdefault(key, default) 方法，或者你可以用 if-else 来判断。

最后一步：返回结果

当所有字符串都遍历完之后，我们的字典也建好了。题目要求返回一个列表的列表（比如 [["ate","eat","tea"], ["nat","tan"], ["bat"]]）。

引导问题：我们怎么把字典里的所有 Value 提取出来，组合成一个符合要求的列表？
提示：字典的 .values() 方法可以获取所有的值，但返回的是一个视图对象，通常我们需要用 list() 转换一下。

💻 动手写写看（填空版）

结合我们前面讨论的所有思路，你可以尝试把下面的代码补全，在本地跑一下试试：

def groupAnagrams(strs):
    anagram_map = {}
    
    for s in strs:
        # 1. 生成 Key（排序并拼接）
        key = ???
        
        # 2. 存入字典
        if key not in anagram_map:
            anagram_map[key] = ???  # 新组，初始化一个列表
        anagram_map[key].append(???) # 把当前单词加进去
        
    # 3. 返回结果，只取字典的值并转为列表
    return ???

字典的操作

1. 字典的基础创建与操作

在 Python 中，创建一个空字典非常简单：

anagram_map = {}

当我们要往里面添加东西时，最基础的方法是通过键（Key）直接赋值：

# 如果键不存在，就是新建；如果键存在，就是覆盖
anagram_map["aet"] = ["ate"] 

此时字典变成了：{"aet": ["ate"]}

如果这个键已经存在了，我们想要往它的列表里追加新元素，可以用 .append()：

anagram_map["aet"].append("eat")

此时字典变成了：{"aet": ["ate", "eat"]}

2. 一步步模拟

假设我们正在遍历数组 ["eat", "tea", "tan", "ate", "nat", "bat"]，字典 anagram_map = {} 的变化过程如下：

• 遍历到 "eat"：

  • 算出 Key 是 "aet"。
  • 去字典里找 "aet"，发现没有。
  • 所以我们要新建一个列表：anagram_map["aet"] = ["eat"]
  • 当前字典：{"aet": ["eat"]}

• 遍历到 "tea"：

  • 算出 Key 是 "aet"。
  • 去字典里找 "aet"，发现有。
  • 所以直接追加：anagram_map["aet"].append("tea")
  • 当前字典：{"aet": ["eat", "tea"]}

• 遍历到 "tan"：

  • 算出 Key 是 "ant"。
  • 去字典里找 "ant"，发现没有。
  • 新建：anagram_map["ant"] = ["tan"]
  • 当前字典：{"aet": ["eat", "tea"], "ant": ["tan"]}

• 遍历到 "ate"：

  • 算出 Key 是 "aet"。
  • 发现有，追加。
  • 当前字典：{"aet": ["eat", "tea", "ate"], "ant": ["tan"]}
• ...依次类推，最后就会变成你写出的那个样子。

3. 如何用代码表达"有"和"没有"？

我们需要一个判断语句：if key not in anagram_map:

具体逻辑如下：

for s in strs:
    key = "".join(sorted(s))  # 这一步是我们刚才讨论的
    
    # 如果 Key 不在字典里（说明是第一次遇到这个字母组合）
    if key not in anagram_map:
        anagram_map[key] = []      # 先创建一个空列表
        anagram_map[key].append(s) # 再把这个单词放进去
        
    # 如果 Key 已经在字典里了
    else:
        anagram_map[key].append(s) # 直接追加进去

其实你可以发现，anagram_map[key].append(s) 这行代码在 if 和 else 里都出现了，为了代码更简洁，我们可以把 if 部分改成这样：

    if key not in anagram_map:
        anagram_map[key] = []      # 如果不存在，先建个空列表占位
        
    anagram_map[key].append(s)     # 不管存不存在，此时里面一定有列表了，直接追加

💡 进阶技巧（Python 专属黑科技）

如果你觉得每次都要判断 if key not in ... 太麻烦了，Python 提供了一个专门针对这种情况的数据结构：collections.defaultdict。

它可以设定默认值，如果 Key 不存在，自动帮你创建一个空列表，省去了判断的步骤：

import collections

def groupAnagrams(strs):
    # 创建一个默认值为 list 的字典，不需要提前初始化
    anagram_map = collections.defaultdict(list)
    
    for s in strs:
        key = "".join(sorted(s))
        # 直接追加，如果 key 不存在，它会自动帮你建一个空列表再追加
        anagram_map[key].append(s) 
        
    # 返回所有分组
    return list(anagram_map.values()) 

接下来交给你：

你可以试着把我们刚才讨论的 if-else 版，或者 defaultdict 版的完整代码写出来。最后一步就是如何返回最终结果了：
你知道用什么方法能把字典里的所有 Value（也就是那些列表）取出来，并转换成一个包含它们的列表（比如 [["eat","tea"], ["tan","nat"]]）吗？

要把我们刚才得到的字典：

anagram_map = {
    "aet": ["ate", "eat", "tea"],
    "ant": ["nat", "tan"],
    "abt": ["bat"]
}

转换为嵌套列表 [["ate", "eat", "tea"], ["nat", "tan"], ["bat"]]，最常用的方法就是提取字典的所有值（Value）。

具体有两种写法，都非常简单：

方法一：使用 .values() 和 list() （最推荐）

result = list(anagram_map.values())

拆解一下这行代码：

1. anagram_map.values()：这个方法会提取字典里所有的"值"，返回一个视图对象（你可以理解为看到了 [["ate", "eat", "tea"], ["nat", "tan"], ["bat"]] 这个整体，但它还不是真正的列表）。
2. list(...)：把刚才提取出来的视图对象，强制转换成一个真正的 Python 列表。

方法二：使用列表推导式（List Comprehension）

如果你喜欢更灵活的方式，可以这样写：

result = [v for v in anagram_map.values()]

这里的 v 代表每一个内层列表，循环一遍拿出来，装进一个新的外层的列表里。

⚠️ 一个容易踩的坑

千万不要直接写 list(anagram_map)！
如果你写 list(anagram_map)，Python 会把字典的 键（Key） 提取出来变成列表，结果会变成：
['aet', 'ant', 'abt'] （这不是题目想要的，题目要的是由单词组成的列表）。

把它放进完整代码里

现在，我们的逻辑彻底闭环了！你可以把这段代码填入 LeetCode 的模板中：

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        anagram_map = {}
        
        for s in strs:
            # 1. 生成唯一的 Key
            key = "".join(sorted(s))
            
            # 2. 存入字典
            if key not in anagram_map:
                anagram_map[key] = []
            anagram_map[key].append(s)
            
        # 3. 提取字典的所有 Value，转换为嵌套列表并返回
        return list(anagram_map.values())

你可以把这段代码复制到 LeetCode 里运行一下。如果通过了，恭喜你完整拿下了这道题！如果在运行中遇到任何奇怪的报错，或者你想知道怎么用"统计字母频次（不排序）"的进阶方法优化它，随时告诉我！

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        str_map = {}
        for s in strs:
            key = "".join(sorted(s))
            if key not in str_map:
                str_map[key] = []
            str_map[key].append(s)
        return list(str_map.values())