C++零基础LeetCode热题100- 49.字母异位词分组

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路

什么是字母异位词？比如"eat"和"tea"，包含的字母完全相同，但顺序不同。
所以判断两个字符串是否是异位词的关键在于，字符组成是否一样。
一个直接的比较方法是对每个字符串进行排序，这样异位词排序后就变成相同的字符串。例如，排序后"eat"和"tea"都会变成"aet"。
这不就是哈希表吗？
哈希表能够在O(1)平均时间复杂度内完成插入和查找操作。通过将排序后的字符串作为键，异位词会被映射到同一个键下，从而实现快速分组。
每次处理一个字符串时，先排序得到键，然后将原字符串添加到对应的列表中。最后遍历哈希表的所有值，组成列表即可。

步骤

1. 创建一个空的哈希表（unordered_map），用来保存已经遍历过的数值及其下标。

2. 遍历输入的字符串数组中的每个字符串。

3. 对当前字符串进行排序，得到一个临时字符串作为键。

4. 将原始字符串插入到哈希表中对应的键的位置的vector里。

5. 遍历完成后，将哈希表中的所有value（即各个vector）收集起来，形成最终的二维数组。

对于示例中的"eat"，排序后的键是"aet"。当处理到"tea"时，同样排序得到"aet"，所以这两个字符串会被放到同一个vector中。

实现代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
     // 哈希表，键为排序后的字符串，值为对应的异位词列表
        unordered_map<string, vector<string>> map;

        // 遍历每个字符串，生成排序后的键并分组
        for (int i = 0; i < strs.size(); ++i) {
            string key = strs[i]; // 拷贝原字符串以生成键
            sort(key.begin(), key.end()); // 排序得到统一格式的键
            map[key].push_back(strs[i]); // 将原字符串加入对应的分组
        }

        // 收集所有分组到结果中
        vector<vector<string>> result;
        for (auto it=map.begin();it!=map.end();it++) { 
            result.push_back(it->second); 
        }

        return result;    
    }
};

代码详解

1.vector<vector<string>> 是 C++中的嵌套容器，表示一个二维动态数组，其每个元素本身也是一个 vector<string>（即一个字符串数组），常用于表示多层嵌套的列表数据。

   外层 vector：表示一个“数组的数组”
   内层 vector<string>：每个元素是一个字符串数组

   可以理解为 一个表格，其中每一行是一个字符串数组，所有行组成一个二维结构。

   需要一维数值集合 → vector<T>（T 为 int、double 等）
   需要一维字符串集合 → vector<string>
   需要二维字符串集合（如分组、表格） → vector<vector<string>>

2.sort(key.begin(), key.end()) sort是C++ 标准库中的一个 排序函数，默认升序，可以对数组、vector 等容器中的元素进行排序

   sort(起始迭代器, 结束迭代器)：
   起始迭代器：指向排序范围的起始位置（包含）
   结束迭代器：指向排序范围的结束位置（不包含）

3.map[key].push_back(strs[i])

   哈希表的常见操作，用于将元素添加到哈希表的value（值）中

   map：一个哈希表（或有序映射），键为 key，值为 vector<string>。

   map[key]：访问哈希表中键为 key 的值（即一个 vector<string>），如果 key 不存在，会自动创建一个键值对，值为空 vector<string>。

   .push_back(strs[i])：将 strs[i] 添加到 map[key] 对应的 vector 中。

4.for (auto it=map.begin();it!=map.end();it++) 遍历哈希表的经典方式

提交结果

注意

这里为什么不能用1.两数之和中的这种形式呢

auto it = map.begin(); // 获取第一个元素的迭代器
if(it!=map.end()){     // 如果哈希表不为空
    result.push_back(it->second);
}

因为这段代码只会将哈希表的第一个分组加入结果，后续分组会被忽略，这是典型的“循环不完整”错误。
两数之和中，由于只有一个vector，所以可以采取这种单一判断。本题有两个vector，是二维的，需要使用循环遍历所有迭代器。

for (auto it = map.begin(); it != map.end(); ++it) {
    result.push_back(it->second);
}