# 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;
}
};