# 49. 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"]
]
``````

Thoughts:

Pick a "normalized" string as a key to store the family of all the anagrams. Here we can use sorted string as the standard one

Code O(nlogn) with standard sort

``````class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map <string, multiset<string>>mp; // use multiset
// to prevent corner case like ["",""]
for(string s: strs){
string t = s;
// "normalize" the string
sort(t.begin(), t.end());
mp[t].insert(s);
}

vector<vector<string>> anagrams;
for(auto m: mp){
vector<string> anagram(m.second.begin(), m.second.end());
anagrams.push_back(anagram);
}

return anagrams;
}
};
``````

Code: O(n) by implementing a unique normalization

``````class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, multiset<string>> mp;
for (string s : strs) {
string t = strSort(s);
mp[t].insert(s);
}
vector<vector<string>> anagrams;
for (auto m : mp) {
vector<string> anagram(m.second.begin(), m.second.end());
anagrams.push_back(anagram);
}
return anagrams;
}
private:
// sorting by constructing a char frequency counter and reversely write it out.
string strSort(string& s) {
int count[26] = {0}, n = s.length();
for (int i = 0; i < n; i++)
count[s[i] - 'a']++;
int p = 0;
string t(n, 'a');
for (int j = 0; j < 26; j++)
for (int i = 0; i < count[j]; i++)
t[p++] += j;
return t;
}
};
``````

Thanks jianchaolifight's solution