MediumCluster words that are rearrangements of the same letters.
Given an array of strings strs, group the anagrams together. Two words are anagrams if one can be formed by rearranging the letters of the other. Return the groups in any order.
Walkthrough
try:
comma- or space-separated words (letters only)
1
function groupAnagrams(strs) {
2
const groups = new Map();
◄
3
for (const word of strs) {
4
const key = word.split('').sort().join('');
5
if (!groups.has(key)) groups.set(key, []);
6
groups.get(key).push(word);
7
}
8
return [...groups.values()];
9
}
no locals yet
words
eatteatanatenatbat
groups (key → words)
(empty)
STEP 0 / 22 · line 2
Start
Create an empty map: a sorted-letter key → the list of words that share it.
Intuition
Anagrams are exactly the words that contain the same letters with the same counts — they only differ in order.
So we need a fingerprint that is identical for anagrams and different otherwise.
Sorting a word’s letters gives such a fingerprint: "eat", "tea", and "ate" all sort to "aet".
Use that sorted string as a hash-map key and append each word to its bucket.
The algorithm
01Create an empty map from key → list of words.
02For each word, sort its characters to build the key.
03If the key has no bucket yet, create an empty one.
04Append the word to its bucket.
05Return all the buckets (the map’s values).
Reference implementation
1
function groupAnagrams(strs) {
2
const groups = new Map(); // sorted key -> list of words
3
for (const word of strs) {
4
const key = word.split('').sort().join('');
5
if (!groups.has(key)) groups.set(key, []);
6
groups.get(key).push(word);
7
}
8
return [...groups.values()];
9
}
Complexity
Time
O(n · k log k) — n words, each of length up to k, sorted once.