49. Group Anagrams

The anagrams share the same pattern if they are sorted. So what I did is to create a hash table where key is the pattern and the value is the anagrams that have the same pattern. So the algorithm becomes obvious that compute the pattern for each anagram and save it into the hash table.

1:  class Solution {  
2:  public:  
3:    vector<vector<string>> groupAnagrams(vector<string>& strs) {  
4:      unordered_map<string, vector<string>> mp;  
5:      for (int i = 0; i < strs.size(); i++) {  
6:        string key = strs[i];  
7:        sort(key.begin(), key.end());  
8:        mp[key].push_back(strs[i]);  
9:      }  
10:      vector<vector<string>> res;  
11:      for (auto it = mp.begin(); it != mp.end(); it++) {  
12:        res.push_back(it->second);  
13:      }  
14:      return res;  
15:    }  
16:  };  

Note I use library sort here which I believe takes O(nlogn) time. Since the anagrams here consist of only 26 lower case letters, we can use bucket sort to compute the pattern which reduce the sorting time to O(n).