力扣-49-字母异位词分组

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

这个题用STL的容器来做会简单很多。

如何判断两个字符串是字母异位词，可以将这些字符串按照字典进行排序，这样排序后的字符串是一样的。

这样引入一个hash，索引是排序后的字符串，值是保存同一字母异位词的结果Vector，最后扫一遍hash输出即可。

#include <unordered_map>

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hash;
        for (const auto& s:strs){
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            hash[tmp].push_back(s);
        }

        int len = hash.size(), index = 0;
        vector<vector<string>> ans(len);
        for (const auto& i : hash){
            ans[index++] = i.second; //将同一字母异位词的所有字符串放入ans
        }
        return ans;
    }
};

这里用了C++11的新特性，简单说明一下。

unordered_map是一个关联容器，同map一样存储键-值，但是元素不会按照任何次序排列，如其名unordered。它也可以通过键key快速访问对应位置的value。

C++11也推出了auto来方便管理容器的迭代器。

for(auto x:range)：拷贝一份range中的元素，而不会改变range中元素；
for(auto& x:range)：引用，可以修改range中元素；
for(const auto&x:range)：当只想读取range中元素时，使用const auto&，它不会进行拷贝，也不会修改range；

原文链接: https://www.cnblogs.com/xiazhenbin/p/13299114.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;

也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/365890

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

力扣-49-字母异位词分组

相关推荐