Group Anagrams
问题描述：
Given an array of strings, group anagrams together.
For example, given: [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”], Return:
[
[
"ate",
"eat",
"tea"],
[
"nat",
"tan"],
[
"bat"]
]
知识补充：
字符串也可以进行排序
string s;
sort(s.
begin(),s.end());
参考答案中很巧妙地字符串中每个字符代表一个数字，通过计算他们的乘法，按题目规则不同的组合得到的结果是不同的，为了确保最后得到的结果不会重叠，用质数来代表每个字母，这样就不会出现不同字符串出现了相同结果。
测试代码：
class Solution {
public:
vector<vector<string>> groupAnagrams(
vector<string>& strs) {
vector<vector<string>> result;
vector<string> res;
string temp =
"";
for(
int i=
0;i<strs.size();i++)
{
int j =
0;
temp = strs[i];
sort(temp.begin(),temp.end());
while(j<res.size())
{
if(res[j]==temp)
{
result[j].push_back(strs[i]);
break;
}
j++;
}
if(j==res.size())
{
res.push_back(temp);
vector<string> s;
s.push_back(strs[i]);
result.push_back(s);
}
}
return result;
}
};
性能：
参考答案：
class Solution {
public:
vector<vector<string>> groupAnagrams(
vector<string>& strs) {
vector<vector<string>> result;
unordered_map<int, int> hashmap;
int idx =
0;
for(
const string& s : strs) {
int hash = get_hash(s);
if(hashmap.find(hash) == hashmap.end()) {
hashmap[hash] = idx++;
result.push_back(
vector<string>{s});
}
else {
result[hashmap[hash]].push_back(s);
}
}
return result;
}
private:
int get_hash(
const string& s) {
const vector<int> prime = {
2,
3,
5,
7,
11,
13,
17,
19,
23,
29,
31,
41,
43,
47,
53,
59,
61,
67,
71,
73,
79,
83,
89,
97,
101,
103};
int a =
1;
for(
char c : s) {
a *= prime[c -
'a'];
}
return a;
}
};
性能：
