49. Group Anagrams (Medium)

Given an array of strings, group anagrams together.

For example, given: ["eat", "tea", "tan", "ate", "nat", "bat"], Return:

[
  ["ate", "eat","tea"],
  ["nat","tan"],
  ["bat"]
]

Note: All inputs will be in lower-case.

Solution: Hash Table 29ms

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string& s: strs) {
            string tmp = s;
            sort(tmp.begin(), tmp.end());
            m[tmp].push_back(s);
        }
        vector<vector<string>> res;
        for (auto& a: m) res.push_back(a.second);
        return res;
    }
};

Solution 2: Sort Functon 29ms

Update: as suggested by yswu1234 in the answer, 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 function strSort below and using it to sort the string achieves the overall running time 72ms for this problem.

class Solution {
    void strSort(string& s) {
        int count[26] = {0}, n = s.size();
        for (int i = 0; i < n; ++i) ++count[s[i]-'a'];
        int p = 0;
        for (int i = 0; i < 26; ++i) {
            for (int j = 0; j < count[i]; ++j) {
                s[p++] = 'a'+i;
            }
        }
    }
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> m;
        for (string& s: strs) {
            string tmp = s;
            strSort(tmp);
            m[tmp].push_back(s);
        }
        vector<vector<string>> res;
        for (auto& a: m) res.push_back(a.second);
        return res;
    }
};