Part 2 · Problems · Arrays and hashing
Group Anagrams
#49 · Medium · LeetCode
Group the words that are anagrams of each other. Any order.
["eat","tea","tan","ate","nat","bat"] -> [["bat"],["nat","tan"],["ate","eat","tea"]]
Ask before coding
- Lowercase only?
- Does output order matter?
Hint
Give every word a key that's the same for all its anagrams.
Approach
The key is the sorted letters (eat, tea, ate all become aet). Map from key to list of words.
Time O(n · k log k), k = word length Space O(n · k)
Watch it run
Solution (JavaScript, tested)
function groupAnagrams(strs) {
const groups = new Map();
for (const s of strs) {
const key = [...s].sort().join(""); // "eat" -> "aet"
if (!groups.has(key)) groups.set(key, []);
groups.get(key).push(s);
}
return [...groups.values()];
}Traps
- For a to z only, a count-based key (26 numbers joined) removes the sort: O(n · k).
Say out loud: This is grouping by a canonical key. Sorted letters is the simplest key.