🧩 LeetCode 49 - Group Anagrams 字母异位词分组

这道题是 LeetCode 字符串 + 哈希表的经典面试题，也非常适合学习 STL 容器和模板编程的实战应用。

✅ 题目简介

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

字母异位词是由相同字母构成，但顺序不同的字符串。

🎯 示例：

输入：["eat", "tea", "tan", "ate", "nat", "bat"]
输出：[["eat","tea","ate"],["tan","nat"],["bat"]]

🧠 解题思路

1. 什么是字母异位词？

字母异位词（Anagram）满足：

举例：

我们发现，只要将字符串排序后相同，它们就是一组异位词！

2. 核心思想（排序 + 哈希）

✅ 完整 C++ 代码实现

#include <vector>
#include <string>
#include <unordered_map>
#include <algorithm>
using namespace std;

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;

        for (string s : strs) {
            string key = s;
            sort(key.begin(), key.end());     // 排序后的字符串作为 key
            hash[key].push_back(s);           // 把原始字符串分到对应组
        }

        vector<vector<string>> result;
        for (auto& pair : hash) {
            result.push_back(pair.second);    // 提取每组异位词
        }

        return result;
    }
};

🧪 示例详解

输入：["eat", "tea", "tan", "ate", "nat", "bat"]

排序过程变成：

原字符串 排序后 key 分组情况
eat aet [“eat”]
tea aet [“eat”, “tea”]
tan ant [“tan”]
ate aet [“eat”, “tea”, “ate”]
nat ant [“tan”, “nat”]
bat abt [“bat”]

最终结果为：

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

🧰 语法讲解小合集

✅ sort 是什么？

sort(key.begin(), key.end());

✅ hash[key].push_back(s) 放哪？

这句放在 for 循环内部，每次处理一个字符串后：

string key = s;
sort(key.begin(), key.end());
hash[key].push_back(s);  // 🌟 按排序后的 key 分组

✅ auto& pair 是什么语法？

for (auto& pair : hash)

✅ 是模板编程吗？

严格来说：

📊 时间与空间复杂度分析

🔁 拓展思考：不用排序可以吗？

当然可以，方式是：

✏️ 小结