知识点

字符串(排序),STL容器(hash表)

思路

对于多个字符串,组成的字符是一样的话,按字典序排序后得到的字符串也一样。所以我们可以利用hashmap来实现对同个集合字符串的存储。

建立映射,按排序后的字符串作为键存储同种类的字符串后,按照题意需要对键值按照字典序排序。

将键值排序后,需要按照此顺序将同个集合内的字符串组合成一个,并加入答案vector中。最后返回答案

细节

对字符串的排序默认按照字典序

本题中,对最终字符串的生成(统一集合内),需要按照题目给的字符串出现顺序来组合,否则会无法通过测试(题意未标明) ##代码c++

#include <unordered_map>
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param strs string字符串vector 
     * @return string字符串vector
     */
    vector<string> groupAnagrams(vector<string>& strs) {
    ///hashmap代表从字符串种类到字符串集合的映射
    unordered_map<string,vector<string>>hashmap;
    //v遍历strs,代表每一个字符串
    for(auto v:strs)
    {
        string t=v;
        sort(t.begin(),t.end());//排序
        hashmap[t].push_back(v);//键对应的值将当前字符串加入集合
    }
    
    vector<string>k;//对键值排序
    for(auto key:hashmap)
    {
        k.push_back(key.first);//遍历hashmap,读取每一个键值
    }
    sort(k.begin(),k.end());//字符串自动排序

    vector<string>ans;//最终答案数组
    for(auto n:k)//n代表当前键值
    {
        vector<string>&now=hashmap[n];
        //利用一个临时vector存储当前键值对应的字符串集合
        string temp="";//当前键值的答案
        for(int i=0;i<now.size();i++)//遍历集合,生成总字符串
        {
            temp+=now[i];
            if(i!=now.size()-1)temp+=',';//注意“,”的处理
        }
        ans.push_back(temp);//放入答案的集合中
    }
    return ans;

    }
};