groupAnagrams

49. 字母异位词分组

分析

核心思想：
- 字母异位词在字母排序后，其排序结果是相同的。例如：
- "eat" 和 "tea" 排序后都为 "aet"
- 因此，可以将排序后的字符串作为键，将所有字母异位词分组存储在一个哈希表中
步骤：
- 遍历字符串数组，对每个字符串进行排序，得到其标准形式
- 将排序后的字符串作为键，将原始字符串加入到对应的哈希表键值中
- 遍历哈希表，提取所有的值（即字母异位词组）

时间复杂度

排序：
- 每个字符串排序的时间复杂度为 O(klogk) ，其中 k 是字符串的平均长度
- 总的排序复杂度为 O(n * klogk) ，其中 n 是字符串数组的大小
哈希表操作：
- 插入和查找操作的平均复杂度为 O(1)

总时间复杂度为 O(n * klogk)

空间复杂度

哈希表存储：需要存储排序后的字符串和对应的原始字符串列表，空间复杂度为 O(n * k)
额外字符串副本：排序时需要创建字符串副本，额外空间复杂度为 O(k)

总空间复杂度为 O(n * k)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


class Solution {
public:
    std::vector<std::vector<std::string>> groupAnagrams(std::vector<std::string>& strs)
    {
        std::vector<std::vector<std::string>> res;  // 存储最终结果
        std::unordered_map<std::string, std::vector<std::string>> hash; // 哈希表用于分组

        // 遍历字符串数组
        for (string str : strs)
        {
            std::string word = str;          // 创建副本以便排序
            std::sort(word.begin(), word.end()); // 排序字符串
            hash[word].push_back(str);  // 将原始字符串加入对应组
        }

        // 遍历哈希表，将值部分（分组结果）加入结果
        for (auto e : hash)
            res.push_back(e.second);

        return res;  // 返回分组后的结果
    }
};