The problem
Given a list of words, group together the words that are anagrams of each other (same letters, different order). Return the groups.
Input: ["eat","tea","tan","ate","nat","bat"] Output: [["eat","tea","ate"], ["tan","nat"], ["bat"]]
Picture it
Picture a row of glass jars, each with a label. To decide where a word goes, sort its letters alphabetically: “tea” becomes “aet”. That sorted spelling is the label on its jar. Words with the same letters always produce the same label, so they land in the same jar. A new label means a new jar.
How to recognise it
- You must sort items into groups, where two items belong together if they are "the same" in some looser sense.
- That sameness can be turned into a key: a value every member of a group shares and no outsider has. Here, anagrams share the same letters in sorted order.
- Grouping by a key is a dictionary from key to list.
- Up to 10^4 words means comparing every word with every other word is too slow.
Start with brute force
Keep a list of groups. For each word, compare it with the first word of every existing group; join the first group it matches, or start a new one.
def group_anagrams_brute(words):
groups = []
for w in words:
for g in groups:
if sorted(g[0]) == sorted(w):
g.append(w)
break
else: # no group matched
groups.append([w])
return groups
With n words of length up to k, each word may be compared with up to n groups, and each comparison sorts two words: O(n² · k log k) time. If no two words are anagrams, n = 10^4 gives about 5 × 10^7 comparisons, each sorting two words of up to 100 letters. Space is O(n · k) for the groups.
From brute force to the idea
- Find the waste. Each word is compared against every group, and each group's first word is re-sorted every time.
- Give every word a label. Sort a word's letters once:
"eat","tea"and"ate"all become"aet". Anagrams get the same label, and non-anagrams never do. - Look the label up. A dictionary from label to list finds the right group in O(1) on average, instead of scanning all groups.
- Join to make it hashable.
sorted(w)returns a list, which cannot be a dictionary key, so the code joins it back into a string. - Let
defaultdictstart groups.jars[key].append(w)creates an empty list the first time a key appears.
This is the key idea: map each word to a canonical key (its sorted letters) and group by that key.
The key idea
Give every word a “signature” that all its anagrams share (its sorted letters) and use it as a dictionary key.
Python solution
def group_anagrams(words):
jars = defaultdict(list)
for w in words:
key = "".join(sorted(w)) # same letters, same key
jars[key].append(w)
return list(jars.values())LeetCode adds the imports for you. To run this on your own machine, put this at the top: from collections import defaultdict
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n² · k log k): each word is compared with every group | O(n · k): the groups hold every word |
| Sorted-letters key (shown code) | O(n · k log k): one sort per word, one O(1) average dictionary step | O(n · k): the keys and the groups |
Here n is the number of words and k the length of the longest word.
Edge cases
- Empty word (
[""]): its key is"", so it forms its own group,[[""]]. Several empty words land in one group. - Single word: returns one group containing it.
- Repeated words (
["ab", "ba", "ab"]): all three go into one group; duplicates are kept, not removed. - Output order: groups appear in the order their first word appeared, and words keep their input order, because Python dictionaries preserve insertion order. LeetCode accepts any order.
- Missing import: the code needs
from collections import defaultdict; without it the call raisesNameError.
Common mistakes
- Using
sorted(w)directly as the key. It is a list, so Python raisesTypeError: unhashable type: 'list'. - Using
set(w)orfrozenset(w)as the key, which forgets counts, so"aab"and"ab"land together. - Returning
jars.values()withoutlist(...). It is a view, not a list, which some callers and tests reject.
A faster key for long words is a tuple of 26 letter counts, which takes O(k) to build instead of O(k log k).
Two lowercase words belong together if shifting every letter of one by the same amount (wrapping from z to a) gives the other: "abc", "bcd" and "xyz" are one group, and "az" and "ba" are another. Group a list of non-empty words this way. Describe your approach, then write it if you like.
Compare with our answer
Find a key that every shift of a word shares. Measure each letter's distance from the first letter, modulo 26. Shifting the whole word changes every letter by the same amount, so the distances stay the same.
from collections import defaultdict
def group_shifted(words):
jars = defaultdict(list)
for w in words:
key = tuple((ord(ch) - ord(w[0])) % 26 for ch in w)
jars[key].append(w)
return list(jars.values())
"az" gives (0, 25) and "ba" gives (0, 25) too, thanks to the modulo. Time O(n · k), space O(n · k).
A strong answer mentions: a key that does not change under the shift, the % 26 for wrap-around, and a tuple (not a list) so the key is hashable.
1. You must group words that use the same set of letters, ignoring repeats, so "aab" and "ab" belong together. Which approach fits?
The key must capture exactly what the groups share: here, which letters appear, not how often. Sorted letters and count tuples both keep the counts, so they would separate "aab" from "ab".
2. Why is the shown code O(n · k log k) rather than O(n²)?
Words are never compared with one another; they are only labelled and looked up. The k log k is the cost of sorting one word. Dictionaries hash their keys, they do not keep them sorted.
3. A learner writes key = sorted(w) without the "".join. What happens when the function runs on ["eat", "tea"]?
Dictionary keys must be hashable, and lists are mutable, so Python raises TypeError: unhashable type: 'list' on the first word. A tuple or a joined string fixes it.
Score 60% or more and the lesson is marked complete.