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