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.

Solution: Categorize by Count

Two strings are anagrams if and only if their character counts (respective number of occurrences of each character) are the same.

Time Complexity: O(N * K). Counting each string is linear in the size of the string, and we count every string.

Space Complexity: O(N*K) the total information content stored in ans.

    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        if (strs.empty()) return {};

        unordered_map<string, vector<string>> m;
        for (auto s: strs) {
            int count[26] = {0};
            for (auto ch: s) count[ch-'a']++;

            string key = "";
            for (int i=0; i<26; i++) {
                while (count[i] != 0) {
                    key += i + 'a';
                    count[i]--;
                }
            }
            m[key].push_back(s);
        }

        vector<vector<string>> ans;
        for (auto it: m) {
            ans.push_back(it.second);
        }
        return ans;
    }

Solution: Categorize by Sorted String

Two strings are anagrams if and only if their sorted strings are equal.

Time Complexity: O(NKlog(K)), where K is the max length of a string in array.

Space Complexity: O(N*K), the total information content stored in ans.

    vector<vector<string>> groupAnagrams(vector<string> &strs) {
        if (strs.empty()) return {};

        unordered_map<string, vector<string>> m;
        for (auto s: strs) {
            string key = s;
            sort(key.begin(), key.end());
            m[key].push_back(s);
        }

        vector<vector<string>> ans;
        for (auto it: m) {
            ans.push_back(it.second);
        }
        return ans;
    }