LeetCode 热门100题-字母异位词分组

2.字母异位词分组

题目描述：

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

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

示例 1:

输入: strs = 

["eat", "tea", "tan", "ate", "nat", "bat"]

输出:

 [["bat"],["nat","tan"],["ate","eat","tea"]]

给定的是vector<string>类型的容器，输出的是vector<vector<string>>类型的容器。

class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string,vector<string>> anagrams;for(const string& str:strs){string sortedstr = str;sort(sortedstr.begin(),sortedstr.end());anagrams[sortedstr].emplace_back(str);}vector<vector<string>> result;for(const auto&pair:anagrams){result.emplace_back(pair.second);}return result;
}
};

实现逻辑：使用for循环遍历strs，对每一个strs[i]对应的单词进行sort排序，如tea和eat都会被排序为aet，对每个单词排序后的结果作为键，如果该键不存在于哈希表中，则创建新元素<key,value>,如果键已存在，则将新单词加入键所对应的vector中，比如开始遍历实例中给的vector容器时，eat和tea经过排序后，都对应aet这个键，遍历eat时，哈希表中开始创建了<aet,{eat}>,当遍历到tea时，哈希表就成了<aet,{eat,tea}>。而后再对遍历完所有strs后的哈希表进行遍历，将其所有元素中存在的值都加入result中，最后result就会成为[["bat"],["nat","tan"],["ate","eat","tea"]]的形式，那么只需返回result就行。

代码解释：

unordered_map<string,vector<string>> anagrams;创建string,vector<string>类型的哈希表anagrams；

for(const string& str:strs)使用for循环对strs中的每一个元素都取别名，const string& str:strs是C++中对容器元素进行遍历的代码。

sort(sortedstr.begin(),sortedstr.end());使用sort对sortedstr进行排序，这里是把sortedstr也当作了一个容器，不过是char类型，按照begin()和end()迭代器作为sort的起始和终结条件。如果sortedstr对应eat，排序后，它就成为aet。

anagrams[sortedstr].emplace_back(str);，按照键：sortedstr往哈希表中插入元素str，其实此时sortedstr也就是str所对应的排序好后的键，string sortedstr = str;这也就是为什么要加这一句代码。

----anagrams[sortedstr]：首先尝试在 anagrams 哈希表中查找键为 sortedstr 的元素。如果找到，则返回该键对应的 vector<string>；如果没有找到，则会创建一个新的 vector<string> 并将其与 sortedstr 键关联起来，然后返回这个新的向量。

----.emplace_back(str)：这是在向由 anagrams[sortedstr] 返回的向量中添加元素的一种方式。emplace_back() 方法与push_back() 方法类似，都是向容器末尾添加元素。但是，emplace_back() 更加高效，因为它是在容器的末尾直接构造对象，而不是先创建对象再复制或移动它进入容器。这意味着如果 emplace_back() 的参数正好匹配要插入元素的构造函数参数，则可以直接在容器的存储空间上进行构造，避免不必要的拷贝或移动操作。

unordered_map<string,vector<string>>  类型的容器 anagrams。这里的pair 实际上代表 anagrams 中的每一个键值对（即每一个元素），其中 pair.first 对应键（在这个场景下是排序后的字符串），而 pair.second 对应值（即一组异位词组成的 vector<string>）。比如经过前面的代码，那么anagrams中元素的存在形式可能是这样的 [{abt,["bat"]},{ant,["nat","tan"]},{aet,["ate","eat","tea"]}],那么每一次遍历pair.second就对应着["bat"]、["nat","tan"]、["ate","eat","tea"]这几个容器。，而后将其插入至result中。

最后将result返回即可。