#49
Group Anagrams
Medium Canonical key + HashMap
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Group the strings so that anagrams end up in the same group.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: put anagrams in the same group.
Why this works: anagrams share the same sorted spelling; use it as a HashMap key.
Example: ["eat","tea","tan","ate","nat","bat"]
"aet" → eat, tea, ate"ant" → tan, nat"abt" → bat
✦Hints open one at a time
All anagrams share the same sorted form.
Use that sorted form (or a letter-count signature) as a HashMap key.
↗Approach
For each word, build a key (sorted characters) and add the word to map[key]. Return the map's values.
</>Solution (Java)
import java.util.*;
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> groups = new HashMap<>();
for (String s : strs) {
char[] chars = s.toCharArray();
Arrays.sort(chars);
String key = new String(chars); // same key for all anagrams
groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
}
return new ArrayList<>(groups.values());
}
}!Common mistake
Using the char[] itself as a map key — arrays use identity equality. Convert to a String.
Complexity
- Time: O(n · k log k), k = max word length (O(n·k) with a count key).
- Space: O(n · k).
Topic: Strings
🎬 Episodes 16–20: video coming soon