https://blog.csdn.net/2601_95366422/article/details/159113241上节课链接一.题目49. 字母异位词分组 - 力扣LeetCode二.思路讲解2.1 思路讲解如果沿用之前判断两个字符串是否为字母异位词的方法需要逐个比较字符出现次数但在本题中字符串数组可能包含多达10^4个字符串两两比较显然不可行。因此我们需要一种更高效的分组策略。字母异位词的本质是由相同字符以不同顺序组成那么如果我们能将每个字符串标准化为一种统一的形式所有互为异位词的字符串就会变成相同的标准化字符串。这个标准化操作就是排序对每个字符串的字符按字典序排序排序后得到的字符串就是该组的唯一标识。例如eat、tea、ate排序后都变成 aet。这样我们就可以利用一个哈希表以排序后的字符串为键将原字符串加入对应的值一个列表中。遍历完所有字符串后哈希表中的所有值即为分组结果。三.代码演示class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { unordered_mapstring,vectorstringhash; vectorvectorstringret; //1.遍历元素然后排序 for(const auto str : strs) { string tmp str; sort(tmp.begin(),tmp.end());//排序 hash[tmp].push_back(str);//把str给排一下序相同的放一起不过放的是原先的元素也就是没有排序的 } //2.取出元素分组 for(const auto [x,y] : hash) { ret.push_back(y); } return ret; } };四.代码讲解一、初始化哈希表为了将互为字母异位词的字符串归类到一起我们需要一个能够快速定位分组的结构。这里使用unordered_mapstring, vectorstring作为哈希表其中键是字符串的排序后形式值是一个列表存放所有与该键对应的原始字符串。这样所有排序后相同的字符串就会被自动归入同一个组。二、遍历每个字符串并排序遍历输入的字符串数组strs对于每一个字符串str执行以下操作创建一个临时字符串tmp并将str复制给它因为我们要排序不能改变原字符串。对tmp进行排序使用sort(tmp.begin(), tmp.end())。排序后所有字母异位词都会变成相同的字符串。例如eat、tea、ate 排序后都变成 aet。以排序后的tmp作为键在哈希表中找到对应的值一个vectorstring然后将原始字符串str添加到该数组中。这里利用了hash[tmp].push_back(str)如果该键不存在会自动创建一个空数组。三、提取分组结果遍历完所有字符串后哈希表中存储了若干键值对每个键对应一组字母异位词。我们需要将这些值即每组字符串的列表收集起来放入最终的结果ret中。使用范围for循环遍历哈希表对于每一对[x, y]将y添加到ret中。注意这里x是排序后的字符串我们不需要它只需要值列表。四、关键细节排序的作用通过排序将字母异位词标准化为同一个字符串从而作为哈希表的键这是本解法的核心。