# 49. Group Anagrams

## Description

Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

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


Example 2:

Input: strs = [""]
Output: [[""]]


Example 3:

Input: strs = ["a"]
Output: [["a"]]


Constraints:

• 1 <= strs.length <= 104
• 0 <= strs[i].length <= 100
• strs[i] consists of lowercase English letters.

## Solutions

Solution 1: Hash Table

1. Traverse the string array, sort each string in character dictionary order to get a new string.
2. Use the new string as key and [str] as value, and store them in the hash table (HashMap<String, List<String>>).
3. When encountering the same key during subsequent traversal, add it to the corresponding value.

Take strs = ["eat", "tea", "tan", "ate", "nat", "bat"] as an example. At the end of the traversal, the state of the hash table is:

key value
"aet" ["eat", "tea", "ate"]
"ant" ["tan", "nat"]
"abt" ["bat"]

Finally, return the value list of the hash table.

The time complexity is $O(n\times k\times \log k)$, where $n$ and $k$ are the lengths of the string array and the maximum length of the string, respectively.

Solution 2: Counting

We can also change the sorting part in Solution 1 to counting, that is, use the characters in each string $s$ and their occurrence times as key, and use the string $s$ as value to store in the hash table.

The time complexity is $O(n\times (k + C))$, where $n$ and $k$ are the lengths of the string array and the maximum length of the string, respectively, and $C$ is the size of the character set. In this problem, $C = 26$.

• class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> d = new HashMap<>();
for (String s : strs) {
char[] t = s.toCharArray();
Arrays.sort(t);
String k = String.valueOf(t);
}
return new ArrayList<>(d.values());
}
}

• class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> d;
for (auto& s : strs) {
string k = s;
sort(k.begin(), k.end());
d[k].emplace_back(s);
}
vector<vector<string>> ans;
for (auto& [_, v] : d) ans.emplace_back(v);
return ans;
}
};

• '''
>>> from collections import defaultdict
>>> d = defaultdict(list)
>>> d["a"]=1
>>> d["b"]=2
>>> d
defaultdict(<class 'list'>, {'a': 1, 'b': 2})
>>> d.values()
dict_values([1, 2])
>>> list(d.values())
[1, 2]

### sorted(str) will return a list of chars
>>> a = "sdfddxyz"
>>> sorted(a)
['d', 'd', 'd', 'f', 's', 'x', 'y', 'z']
>>> "".join(sorted(a))
'dddfsxyz'
'''

class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
d = defaultdict(list)
for s in strs:
k = "".join(sorted(s))
d[k].append(s)
return list(d.values())


• func groupAnagrams(strs []string) (ans [][]string) {
d := map[string][]string{}
for _, s := range strs {
t := []byte(s)
sort.Slice(t, func(i, j int) bool { return t[i] < t[j] })
k := string(t)
d[k] = append(d[k], s)
}
for _, v := range d {
ans = append(ans, v)
}
return
}

• function groupAnagrams(strs: string[]): string[][] {
const d: Map<string, string[]> = new Map();
for (const s of strs) {
const k = s.split('').sort().join('');
if (!d.has(k)) {
d.set(k, []);
}
d.get(k)!.push(s);
}
return Array.from(d.values());
}


• using System.Collections.Generic;

public class Comparer : IEqualityComparer<string>
{
public bool Equals(string left, string right)
{
if (left.Length != right.Length) return false;

var leftCount = new int[26];
foreach (var ch in left)
{
++leftCount[ch - 'a'];
}

var rightCount = new int[26];
foreach (var ch in right)
{
var index = ch - 'a';
if (++rightCount[index] > leftCount[index]) return false;
}

return true;
}

public int GetHashCode(string obj)
{
var hashCode = 0;
for (int i = 0; i < obj.Length; ++i)
{
hashCode ^= 1 << (obj[i] - 'a');
}
return hashCode;
}
}

public class Solution {
public IList<IList<string>> GroupAnagrams(string[] strs) {
var dict = new Dictionary<string, List<string>>(new Comparer());
foreach (var str in strs)
{
List<string> list;
if (!dict.TryGetValue(str, out list))
{
list = new List<string>();
}
}
foreach (var list in dict.Values)
{
list.Sort();
}
return new List<IList<string>>(dict.Values);
}
}

• use std::collections::HashMap;

impl Solution {
pub fn group_anagrams(strs: Vec<String>) -> Vec<Vec<String>> {
let mut map = HashMap::new();
for s in strs {
let key = {
let mut arr = s.chars().collect::<Vec<char>>();
arr.sort();
arr.iter().collect::<String>()
};
let val = map.entry(key).or_insert(vec![]);
val.push(s);
}
map.into_iter()
.map(|(_, v)| v)
.collect()
}
}