49. 字母异位词分组

题目链接（中等）

题目描述

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

字母异位词 是通过重新排列不同单词或短语的字母而形成的单词或短语，并使用所有原字母一次。

数据范围：

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

示例

示例 1：

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

• strs 中没有字符串可以通过重新排列来形成 "bat"；
• "nat" 和 "tan" 是字母异位词，因为它们可以重新排列以形成彼此；
• "ate"、"eat" 和 "tea" 是字母异位词。

示例 2：

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

示例 3：

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

方法一：排序作为哈希键

思路及解法

两个字符串互为字母异位词，当且仅当它们包含的字母相同。因此，把两个字符串分别排序后得到的字符串一定相同，可以把排序后的字符串作为哈希表的键。

遍历每个字符串，对其排序得到 key，把原字符串加入 map[key] 对应的列表中。遍历结束后，哈希表中的每个值就是一组字母异位词。

代码

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        mp = defaultdict(list)
        for s in strs:
            key = ''.join(sorted(s))
            mp[key].append(s)
        return list(mp.values())

复杂度分析

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

方法二：计数作为哈希键

思路及解法

互为字母异位词的两个字符串，相同字母出现的次数一定相同。可以用长度为 26 的数组统计每个字母出现的次数，把这个数组作为哈希表的键。

由于 列表不能哈希，需要转成 tuple 才能作为字典的键：

mp[tuple(counts)].append(s)

也可以把计数数组拼成一个字符串（用分隔符隔开），效果相同，但 tuple 更直接。

代码

from collections import defaultdict

class Solution:
    def groupAnagrams(self, strs: list[str]) -> list[list[str]]:
        mp = defaultdict(list)
        for s in strs:
            counts = [0] * 26
            for ch in s:
                counts[ord(ch) - ord('a')] += 1
            # list 不能哈希，转成 tuple 才能作为键
            mp[tuple(counts)].append(s)
        return list(mp.values())

复杂度分析

• 时间复杂度：$O(n(k + |\Sigma|))$，其中 $n$ 是字符串数量，$k$ 是最大长度，$|\Sigma| = 26$ 是字符集大小。每个字符串统计计数需要 $O(k)$，生成键需要 $O(|\Sigma|)$。
• 空间复杂度：$O(n(k + |\Sigma|))$，哈希表存储全部字符串。

两种方法对比

方法	键	时间	空间	特点
排序	排序后的字符串	$O(nk \log k)$	$O(nk)$	代码最短，通用性强
计数	长度为 26 的 tuple	$O(n(k +	\Sigma	))$	$O(n(k +	\Sigma	))$	时间更优，适合字符集固定的场景

推荐：

• 面试时优先写计数法，因为它体现了对哈希键的理解，且不依赖排序；
• 日常刷题用排序法，代码更短。

总结

• 字母异位词的核心特征：字母种类和数量完全相同；
• 用哈希表分组，关键是找到一个能代表“字母组成”的唯一键；
• 排序后的字符串和字母计数数组都可以作为键；
• Python 中 list 不可哈希，需要转 tuple 或 str。