Group Anagrams
MediumArrays and hashing
You are given an array of lowercase words. Put the words that are anagrams of each other (the same letters, each the same number of times) into one group, and return the groups.
The groups can come back in any order, and so can the words inside each group.
Examples
Input: words = ["stop", "pots", "tops", "cat", "act", "dog"] Output: [["stop", "pots", "tops"], ["cat", "act"], ["dog"]]
stop, pots and tops share their letters; so do cat and act. dog has no partner.
Input: words = ["solo"] Output: [["solo"]]
One word makes one group.
Constraints
1 ≤ words.length ≤ 10⁴0 ≤ words[i].length ≤ 100- Words use lowercase English letters only.
Stuck?
Hint 1
Two words are anagrams exactly when their letters, sorted, give the same string. Use that string as a key.
Hint 2
To skip the sort, count the 26 letters and join the counts into the key.
The idea
Anagrams are the same letters in a different order, so sorting the letters of each word removes the only difference between them. Words whose sorted letters match are anagrams, and that sorted string can key a Map whose values are the groups.
Time O(n · k log k) for n words of length kExtra space O(n · k)
Try it again with the idea in mind, or go through the code one step at a time.
The code, step by step
Step 1 of 4
groups maps a key to the list of words that share it. Each key ends up as one group.
function groupAnagrams(words) { const groups = new Map(); for (const word of words) { const key = [...word].sort().join(''); if (!groups.has(key)) groups.set(key, []); groups.get(key).push(word); } return [...groups.values()];}The trap
Grouping words by length puts every set of anagrams together, since anagrams always have the same length. So an input where each length belongs to one family passes. But two words of the same length with different letters also land in one group, which is wrong.
function groupAnagrams(words) { const groups = {}; for (const w of words) (groups[w.length] ||= []).push(w); // by length, not letters return Object.values(groups);}