# Group Anagrams

StringHash Table

## # Solution

Let n\$ be the length of strs, and $k$ the maximum length of a string in strs.

### # Categorize by Sorted String

Use the sorted string as dictionary key.

Sorting each string takes $O(k \log k)$ time. The for loop does it $n$ times.

Complexity

time: $O(nk \log k)$
space: $O(nk)$

from collections import defaultdict
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dct = defaultdict(list)
# make sure the key string is sorted
for s in strs:
dct[tuple(sorted(s))].append(s)
return dct.values()

1
2
3
4
5
6
7

### # Categorize by Count

Use the char count as dictionary key.

Counting each string is $O(k)$. The for loop does it $n$ times.

Complexity

time: $O(nk)$
space: $O(nk)$

from collections import defaultdict
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
dct = defaultdict(list)
# make sure the key string is sorted
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
dct[tuple(count)].append(s)
return dct.values()

1
2
3
4
5
6
7
8
9
10