MediumBlind75StringHash Table
Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
Examples
Input
strs = ["eat","tea","tan","ate","nat","bat"]
Output
[["bat"],["nat","tan"],["ate","eat","tea"]]
Group anagrams together.
Constraints
- •
1 <= strs.length <= 10^4 - •
0 <= strs[i].length <= 100 - •
strs[i] consists of lowercase English letters.
Approaches
For each string, sort it and check all other strings for anagram match.
CodeT: O(n^2 * k log k) | S: O(n * k)
def group_anagrams(strs):
result = []
used = [False] * len(strs)
for i in range(len(strs)):
if used[i]:
continue
group = [strs[i]]
used[i] = True
for j in range(i + 1, len(strs)):
if not used[j] and sorted(strs[i]) == sorted(strs[j]):
group.append(strs[j])
used[j] = True
result.append(group)
return resultUse the sorted version of each string as the key in a hash map.
CodeT: O(n * k log k) | S: O(n * k)
def group_anagrams(strs):
from collections import defaultdict
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())Use a tuple of character counts as the hash map key to avoid sorting.
Diagram
strs = ['eat','tea','tan','ate','nat','bat']
'eat' -> count tuple -> grouped with 'tea','ate'
'tan' -> count tuple -> grouped with 'nat'
'bat' -> count tuple -> alone
CodeT: O(n * k) | S: O(n * k)
def group_anagrams(strs):
from collections import defaultdict
groups = defaultdict(list)
for s in strs:
count = [0] * 26
for c in s:
count[ord(c) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())Complexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n^2 * k log k) | O(n * k) | For each string, sort it and check all other strings for anagram match. |
| Sorted Key Hash Map | O(n * k log k) | O(n * k) | Use the sorted version of each string as the key in a hash map. |
| Character Count Key | O(n * k) | O(n * k) | Use a tuple of character counts as the hash map key to avoid sorting. |
Brute Force
T: O(n^2 * k log k)S: O(n * k)
For each string, sort it and check all other strings for anagram match.
Sorted Key Hash Map
T: O(n * k log k)S: O(n * k)
Use the sorted version of each string as the key in a hash map.
Character Count Key
T: O(n * k)S: O(n * k)
Use a tuple of character counts as the hash map key to avoid sorting.
Common Mistakes
Using a list as dict key (lists are not hashable, must use tuple)
Not handling empty strings properly
Forgetting to use defaultdict