知识点
字符串(排序),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;
}
};