Group a list of words into anagrams.
Sort each word's characters to get a canonical key, then bucket words by that key using a hash map. This turns an O(n²) brute-force comparison into a clean O(n · k log k) single pass, where k is the max word length.
How to think about it
Recognise the pattern
The moment you hear “group things that are equivalent under some transformation,” reach for a hash map with a canonical key. Anagrams are equivalent under character-sorting: "eat", "tea", and "ate" all sort to "aet". That sorted string becomes the bucket key — no pair-wise comparison needed.
Build the approach step by step
Brute force: compare every pair of words, check if one is a permutation of the other (sort both and compare). That is O(n² · k log k) time and fiddly to implement correctly.
The insight: instead of comparing pairs, map each word to a fingerprint it shares with all its anagram siblings. Sorted characters are the simplest fingerprint — two words are anagrams if and only if their sorted forms are identical.
Step-by-step:
- Create a
defaultdict(list). - For each word, compute
key = "".join(sorted(word)). - Append the original word to
buckets[key]. - Return
list(buckets.values()).
One pass, one dict — done.
Complexity
| Value | Why | |
|---|---|---|
| Time | O(n · k log k) | Sorting each of the n words of length k |
| Space | O(n · k) | Storing all words in the hash map |
The log k comes from sorting characters; if you replace sorting with a character-frequency tuple (26 ints for lowercase ASCII), you can get O(n · k) time with a slightly heavier constant.