# 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.

# Solution

Approach 1: Map each string to the key by sorting its letters (e.g., via counting sort).

# Code (Python)

Approach 1:

import collections
class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        anagrams = collections.defaultdict(list)
        for string in strs:
            anagrams[self._normalize(string)].append(string)
        
        return list(anagrams.values())
    
    def _normalize(self, string):
        key = [0] * 26
        for char in string:
            key[ord(char) - ord('a')] += 1
        return tuple(key)

# Code (C++)

Approach 1:

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        vector<vector<string>> group;
        unordered_map<string,int> groupMap;
        for (int i = 0; i < strs.size(); ++i)
        {
            string key = strs[i];
/*
            // Sort.
            std::sort(key.begin(), key.end());
*/
            // Counting sort.
            int letterCount[26] = {0};
            for (int j = 0; j < key.size(); ++j)
            {
                letterCount[key[j] - 'a']++;
            }
            key = "";
            for (int j = 0; j < 26; ++j)
            {
                key += string('a' + j, letterCount[j]);
            }
            //

            if (groupMap.find(key) != groupMap.end())
            {
                group[groupMap[key]].push_back(strs[i]);
            }
            else
            {
                vector<string> subgroup;
                subgroup.push_back(strs[i]);
                group.push_back(subgroup);
                groupMap[key] = group.size() - 1;
            }
        }
        return group;
    }
};