The function signature has been updated to return a more intuitive vector<vector<string>>which treats a single string as a group of anagrams consisting of only itself.
The idea is to use an unordered_map to store those strings that are anagrams. We use the sorted string as the key and the string itself as the value. The strings are stored in a multisetsince there may be duplicates. Moreover, multiset will sort them by default as we desire.
The code is as follows.
1 class Solution { 2 public: 3 vector<vector<string>> groupAnagrams(vector<string>& strs) { 4 unordered_map<string, multiset<string>> mp; 5 for (string s : strs) { 6 string t = s; 7 sort(t.begin(), t.end()); 8 mp[t].insert(s); 9 } 10 vector<vector<string>> anagrams; 11 for (auto m : mp) { 12 vector<string> anagram(m.second.begin(), m.second.end()); 13 anagrams.push_back(anagram); 14 } 15 return anagrams; 16 } 17 };
Update: general sort takes O(nlogn) time. In this problem, since the string only contains lower-case alphabets, we can write a sorting function using counting sort (O(n) time) to speed up the sorting process. I write a string sorting functionstrSort below and using it to sort the string achieves the overall running time 72ms for this problem while the above code takes 76ms.
1 class Solution { 2 public: 3 vector<vector<string>> groupAnagrams(vector<string>& strs) { 4 unordered_map<string, multiset<string>> mp; 5 for (string s : strs) { 6 string t = strSort(s); 7 mp[t].insert(s); 8 } 9 vector<vector<string>> anagrams; 10 for (auto m : mp) { 11 vector<string> anagram(m.second.begin(), m.second.end()); 12 anagrams.push_back(anagram); 13 } 14 return anagrams; 15 } 16 private: 17 string strSort(string& s) { 18 int count[26] = {0}, n = s.length(); 19 for (int i = 0; i < n; i++) 20 count[s[i] - 'a']++; 21 int p = 0; 22 string t(n, 'a'); 23 for (int j = 0; j < 26; j++) 24 for (int i = 0; i < count[j]; i++) 25 t[p++] += j; 26 return t; 27 } 28 };
