LeetCode 热题 100 | 49. 字母异位词分组 (Group Anagrams)

题目描述

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词（通常每个字母使用次数必须相同）。

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

---

解题思路：哈希表 + 排序 (Sorting)

这道题的核心在于：如何高效地判断两个字符串是否是字母异位词？

核心逻辑

字母异位词虽然字符顺序不同，但如果对它们进行 排序 (Sort)，得到的结果一定是完全相同的。例如： * "eat" 排序后为 "aet" * "tea" 排序后为 "aet" * "ate" 排序后为 "aet"

因此，我们可以将 “排序后的字符串” 作为哈希表（std::unordered_map）的 Key，将 “原始字符串组成的数组” 作为 Value。

算法步骤

1. 遍历字符串数组 strs。
2. 对于每个字符串，先拷贝一份并进行排序，得到 key。
3. 将原始字符串存入 mp[key] 对应的 vector 中。
4. 遍历完成后，将哈希表中所有的 vector 提取出来即为最终答案。

---

代码实现 (C++)

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        // key: 排序后的字符串, value: 属于该分组的所有原始字符串
        unordered_map<string, vector<string>> mp;

        for(string& str : strs) {
            string k = str;
            // 关键点：排序后的字符串是唯一的标识符
            sort(k.begin(), k.end());
            mp[k].emplace_back(str);
        }

        vector<vector<string>> ans;
        // 提取哈希表中的所有结果
        for(auto it = mp.begin(); it != mp.end(); ++it) {
            ans.emplace_back(it->second);
        }

        return ans;
    }
};

复杂度分析

时间复杂度

T(n) = O(n ⋅ klog k)

其中 n是字符串数组的长度，k是字符串的最大长度。我们需要遍历 n个字符串，每个字符串排序的时间复杂度是 O(k log k)。

空间复杂度

S(n) = O(n ⋅ k)

我们需要哈希表来存储所有的字符串。