字母异位词分组 | 秋招知识库

题目链接 · 灵神原题解（署名来源）

题意解读

如果两个字符串从小到大排序后相等，那么两个字符串就互为字母异位词，否则不是。

例如 $aab, aba, baa$ 排序后都是 $aab$ ，所以 $aab, aba, baa$ 互为字母异位词。

示例 1 是怎么算的？

输入 $strs = [eat, tea, tan, ate, nat, bat]$ 。

每个字符串各自排序，得到 $aet, aet, ant, aet, ant, abt$ 。

把排序后相同的字符串分到同一组：

排序后是 $aet$ 的字符串，排序前是 $eat, tea, ate$ 。
排序后是 $ant$ 的字符串，排序前是 $tan, nat$ 。
排序后是 $abt$ 的字符串，排序前是 $bat$ 。

因此，示例 1 返回的二维列表中，包含三个列表，分别为

$[eat, tea, ate]$ 。
$[tan, nat]$ 。
$[bat]$ 。

三个列表的顺序随意。

算法

用哈希表分组，把排序后的字符串当作哈希表的 key，排序前的字符串加到对应的列表中（哈希表的 value）。

最后把哈希表的所有 value 加到一个列表中返回。

Python 解法1C++ 解法1

python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = {}  # 用 defaultdict 的写法见【Python3 写法二】
        for s in strs:
            sorted_s = ''.join(sorted(s))  # 把 s 排序，作为 dict 的 key
            if sorted_s not in d:  # 首次遇到 sorted_s
                d[sorted_s] = []  # 创建列表
            d[sorted_s].append(s)  # 排序后相同的字符串，保存到同一组中
        return list(d.values())  # 哈希表的所有 value 就是分组结果

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        d = defaultdict(list)  # 如果 key 不在字典中，defaultdict 会自动创建一个空列表作为 value
        for s in strs:
            sorted_s = ''.join(sorted(s))  # 把 s 排序，作为 defaultdict 的 key
            d[sorted_s].append(s)  # 排序后相同的字符串，保存到同一组中
        return list(d.values())  # 哈希表的所有 value 就是分组结果

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string& s : strs) {
            string sorted_s = s;
            ranges::sort(sorted_s); // 把 s 排序，作为哈希表的 key
            m[sorted_s].push_back(s); // 排序后相同的字符串，保存到同一组中
        }

        vector<vector<string>> ans;
        ans.reserve(m.size()); // 预分配空间
        for (auto& [_, value] : m) {
            ans.push_back(value); // 哈希表的所有 value 就是分组结果
        }
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n m \log m)$ ，其中 $n$ 为 $strs$ 的长度， $m$ 为 $strs [i]$ 的长度。每个字符串排序需要 $O (m \log m)$ 的时间，有 $n$ 个字符串，所以总的时间复杂度为 $O (n m \log m)$ 。
空间复杂度： $O (n m)$ 。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

题意解读 ​

示例 1 是怎么算的？ ​

算法 ​

复杂度分析 ​

分类题单 ​

题意解读

示例 1 是怎么算的？

算法

复杂度分析

分类题单