49. Group Anagrams

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
  ["ate","eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note:

• All inputs will be in lowercase.

• The order of your output does not matter.

用STL的sort來把每個字排序。

// Hashtable + STL sort
vector<vector<string>> groupAnagrams(vector<string>& strs) { // time: O(n*str_len*log(str_len)); space: O(n)
    unordered_map<string, vector<string> > m;
    for (string& str : strs) {
        string word = str;
        sort(word.begin(), word.end());
        m[word].push_back(str);
    }
    vector<vector<string> > res;
    for (auto it = m.begin(); it != m.end(); ++it) {
        res.push_back(it->second);
    }
    return res;
}

也可以自己寫一個簡易的sort來排序string，time complexity比較好。

// Hashtable + sort
string strSort(string& s) {
    vector<int> count(26, 0);
    int n = s.length();
    for (char c : s) {
        ++count[c - 'a'];
    }
    int pos = 0;
    string res(n, 'a');
    for (int i = 0; i < 26; ++i) {
        for (int j = 0; j < count[i]; ++j) {
            res[pos++] += i;
        }
    }
    return res;
}
vector<vector<string>> groupAnagrams(vector<string>& strs) { // time: O(n * str_len); space: O(n)
    unordered_map<string, vector<string> > group;
    for (string& str : strs) {
        string word = strSort(str);
        group[word].push_back(str);
    }
    vector<vector<string> > res;
    for (auto it = group.begin(); it != group.end(); ++it) {
        res.push_back(it->second);
    }
    return res;
}