网站快照描述,搜索营销,永州建设学校官方网站,会员管理系统怎么用2.字母异位词分组
题目描述#xff1a;
给你一个字符串数组#xff0c;请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan
给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs [eat, tea, tan, ate, nat, bat] 输出:[[bat],[nat,tan],[ate,eat,tea]]
给定的是vectorstring类型的容器输出的是vectorvectorstring类型的容器。
class Solution {
public:
vectorvectorstring groupAnagrams(vectorstring strs) {unordered_mapstring,vectorstring anagrams;for(const string str:strs){string sortedstr str;sort(sortedstr.begin(),sortedstr.end());anagrams[sortedstr].emplace_back(str);}vectorvectorstring result;for(const autopair: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_mapstring,vectorstring anagrams;创建string,vectorstring类型的哈希表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 的元素。如果找到则返回该键对应的 vectorstring如果没有找到则会创建一个新的 vectorstring 并将其与 sortedstr 键关联起来然后返回这个新的向量。
----.emplace_back(str)这是在向由 anagrams[sortedstr] 返回的向量中添加元素的一种方式。emplace_back() 方法与push_back() 方法类似都是向容器末尾添加元素。但是emplace_back() 更加高效因为它是在容器的末尾直接构造对象而不是先创建对象再复制或移动它进入容器。这意味着如果 emplace_back() 的参数正好匹配要插入元素的构造函数参数则可以直接在容器的存储空间上进行构造避免不必要的拷贝或移动操作。
unordered_mapstring,vectorstring 类型的容器 anagrams。这里的pair 实际上代表 anagrams 中的每一个键值对即每一个元素其中 pair.first 对应键在这个场景下是排序后的字符串而 pair.second 对应值即一组异位词组成的 vectorstring。比如经过前面的代码那么anagrams中元素的存在形式可能是这样的 [{abt,[bat]},{ant,[nat,tan]},{aet,[ate,eat,tea]}],那么每一次遍历pair.second就对应着[bat]、[nat,tan]、[ate,eat,tea]这几个容器。而后将其插入至result中。
最后将result返回即可。
