【LeetCode】字母异位词分组

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

字母异位词是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]

示例 2:

输入: strs = [“”]
输出: [[“”]]

示例 3:

输入: strs = [“a”]
输出: [[“a”]]

核心思路：

使用unordered_map（哈希表）将排序后的字符串映射到一个字符串列表中。哈希表的键是排序后的字符串，值是所有与该键对应的原始字符串组成的列表。

#include <iostream>
#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>> anagrams;
        for (const auto& s : strs)
        {
            string sort_str = s;
            sort(sort_str.begin(), sort_str.end());
            // 建立哈希映射
            anagrams[sort_str].push_back(s);
        }
        // 返回结果
        vector<vector<string>> result;
        for (auto& pair : anagrams)
        {
            result.push_back(pair.second);
        }
        return result;
    }
};
int main() 
{
    Solution sol;

    vector<string> strs1 = { "eat", "tea", "tan", "ate", "nat", "bat" };
    vector<vector<string>> result1 = sol.groupAnagrams(strs1);

    // 打印结果
    cout << "示例 1 结果:" << endl;
    for (const auto& group : result1) 
    {
        for (const auto& word : group) 
        {
            cout << word << " ";
        }
        cout << endl;
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49