LeetCode Hot100 C++ 哈希 49.字母异位词分组

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

给你一个字符串数组，请你将字母异位词组合在一起。可以按任意顺序返回结果列表。
字母异位词是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]
输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]
示例 2:
输入: strs = [“”]
输出: [[“”]]
示例 3:
输入: strs = [“a”]
输出: [[“a”]]
提示：
1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母

思路：
对每个单词拷贝一个副本，然后对单词的副本进行排序，排序后相等的单词存到同一个数组中。这里借用一个hash表，排序后的单词作为hash表的key。

对于strs = [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]，怎么排序的？

遍历每个字符串，对每个字符串进行排序:

对于 “eat”，排序后得到 “aet”
对于 “tea”，排序后得到 “aet”
对于 “tan”，排序后得到 “ant”
对于 “ate”，排序后得到 “aet”
对于 “nat”，排序后得到 “ant”
对于 “bat”，排序后得到 “abt”

将排序后的字符串作为键，将原始字符串进行分组:

键 “aet” 对应的字母异位词组为：[“eat”, “tea”, “ate”]
键 “ant” 对应的字母异位词组为：[“tan”, “nat”]
键 “abt” 对应的字母异位词组为：[“bat”]
在这里插入图片描述

代码：

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {vector<vector<string>> res;unordered_map<string, vector<string>> u_mapRes;for (auto& str : strs) {//对副本进行排序string key(str);sort(key.begin(), key.end());//存到hash表中u_mapRes[key].push_back(str);}for (auto& a : u_mapRes) {res.push_back(a.second);}return res;}
};

PS:
GPT4O逐行解析：

1. 函数定义
class Solution: 定义一个名为 Solution 的类。
public:: public 访问修饰符，表示后续成员可以在类外部访问。
vector<vector<string>> groupAnagrams(vector<string>& strs): 定义 groupAnagrams 函数，它是 Solution 类的一个成员函数。
返回值类型是 vector<vector<string>>，即一个二维字符串数组。
参数 vector<string>& strs 是一个引用类型的字符串数组，代表输入的字符串集合。2. 初始化变量
vector<vector<string>> res: 定义一个二维字符串数组 res，用于存储最终的分组结果。
unordered_map<string, vector<string>> u_mapRes: 定义一个哈希表 u_mapRes，它的键（string 类型）用于存储排序后的字符串，值（vector<string> 类型）用于存储对应的字母异位词列表。3. 遍历输入字符串数组
for (auto& str : strs): 使用范围 for 循环遍历输入字符串数组 strs，str 代表当前遍历到的字符串。
string key(str): 创建一个新的字符串 key，它是 str 的副本。此时，key 与 str 内容相同，但后续操作不会影响 str 本身。
sort(key.begin(), key.end()): 对 key 进行排序，目的是将 key 转换为一个字母顺序一致的字符串，作为字母异位词的唯一标识。例如，"eat" 在排序后变为 "aet"。
u_mapRes[key].push_back(str): 使用 key 作为哈希表 u_mapRes 的键，将原始字符串 str 添加到 u_mapRes[key] 的字符串向量中。这样，具有相同字符组成的字符串会被归入同一组。4. for (auto& pair : u_mapRes): 使用范围 for 循环遍历 unordered_map u_mapRes，pair 是每个键值对（key 和 value），其中 pair.first 是键，pair.second 是对应的字符串向量。
res.push_back(pair.second): 将 pair.second（即一个字母异位词组）添加到结果 res 中。5. 返回结果
return res: 返回最终的分组结果 res，这是一个包含多个字母异位词组的二维字符串数组。以 strs = ["eat", "tea", "tan", "ate", "nat", "bat"] 为例，执行过程如下：
遍历字符串 strs，按排序后的字符串将字母异位词存入 unordered_map：
"eat" 排序后 "aet"，键 "aet" 对应 ["eat"]
"tea" 排序后 "aet"，键 "aet" 对应 ["eat", "tea"]
继续这个过程，unordered_map 最终会包含：
"aet" -> ["eat", "tea", "ate"]
"ant" -> ["tan", "nat"]
"abt" -> ["bat"]
遍历 unordered_map，将每组字母异位词添加到 res 中，得到最终结果