015. Group Anagrams

Why this mechanism works

Convert an equivalence relation into a canonical key. Sorting a word's characters yields the same tuple exactly when its multiplicities match another word's. A dictionary then gathers each equivalence class without comparing every pair of words.

State and boundaries

groups maps a sorted-character tuple to the words seen with that signature, in encounter order.

Protocol

1. Start an empty dictionary.
2. Sort each word's characters into a tuple.
3. Create its group if absent.
4. Append the original word.
5. Return dictionary groups in insertion order.

Visualization

eat, tea, ate -> ('a','e','t')
tan, nat      -> ('a','n','t')
bat           -> ('a','b','t')

Python implementation

def group_anagrams(words):
    groups = {}
    for word in words:
        key = tuple(sorted(word))
        groups.setdefault(key, []).append(word)
    return list(groups.values())

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 group_anagrams: groups = {}
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={}

L3 group_anagrams: for word in words:
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={}; word='eat'

L4 group_anagrams: key = tuple(sorted(word))
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={}; word='eat'; key=('a', 'e', 't')

L5 group_anagrams: groups.setdefault(key, []).append(word)
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat']}; word='eat'; key=('a', 'e', 't')

L3 group_anagrams: for word in words:
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat']}; word='tea'; key=('a', 'e', 't')

L5 group_anagrams: groups.setdefault(key, []).append(word)
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea']}; word='tea'; key=('a', 'e', 't')

L3 group_anagrams: for word in words:
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea']}; word='tan'; key=('a', 'e', 't')

L4 group_anagrams: key = tuple(sorted(word))
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea']}; word='tan'; key=('a', 'n', 't')

... 6 intermediate state changes omitted ...

L5 group_anagrams: groups.setdefault(key, []).append(word)
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea', 'ate'], ('a', 'n', 't'):['tan', 'nat']}; word='nat'; key=('a', 'n', 't')

L3 group_anagrams: for word in words:
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea', 'ate'], ('a', 'n', 't'):['tan', 'nat']}; word='bat'; key=('a', 'n', 't')

L4 group_anagrams: key = tuple(sorted(word))
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea', 'ate'], ('a', 'n', 't'):['tan', 'nat']}; word='bat'; key=('a', 'b', 't')

L5 group_anagrams: groups.setdefault(key, []).append(word)
words=['eat', 'tea', 'tan', 'ate', 'nat', 'bat']; groups={('a', 'e', 't'):['eat', 'tea', 'ate'], ('a', 'n', 't'):['tan', 'nat'], ('a', 'b', 't'):['ba...; word='bat'; key=('a', 'b', 't')

L2 group_anagrams: groups = {}
words=[]; groups={}

Why the solution is correct

Equal keys imply equal sorted sequences and therefore equal character counts. Anagrams necessarily produce equal keys. Each word is appended once to its unique correct group, and dictionary insertion order enforces the requested group ordering.

Time and space

O(sum(L_i log L_i)) sorting time, plus O(sum L_i) key/output-reference storage in the worst case.

Common mistakes

A list cannot be a dictionary key. Using a set signature incorrectly groups ab with aab.

Reasoning card

Transfer exercise

For lowercase English letters only, replace sorting with a 26-count tuple and derive the new cost.