Group anagrams with canonical keys in Python

Why this matters

A lot of real programs need to sort a pile of items into bins. A shop groups orders by customer. A log tool groups errors by message. A spell checker groups words by their letters. In each case the same question comes up: "Which items belong together?" A dict answers it well when you can compute one value, called a key, for each item, so that items that belong together get the same key.

This lesson uses a classic puzzle to teach that idea. The puzzle is to group words that are anagrams of each other. The method is called a canonical key. "Canonical" means "in its standard form." A canonical key is a standard form that every member of a group produces, so equal keys mean the items belong together.

You will see two keys for the same job. One key is the word with its letters sorted. The other key is the count of each letter. You will build both, run them, see the one place where Python's rules change the design, and learn how to choose between them.

The problem: which words are anagrams?

An anagram is a word made by rearranging the letters of another word. "eat", "tea" and "ate" are anagrams of each other, because each uses one a, one e and one t. "tan" and "nat" are anagrams. "bat" is not an anagram of any of them, because it has a b.

The task is this. You get a list of words. You return the groups, where each group holds the words that are anagrams of each other. For the input below, the groups are three.

input:  eat, tea, tan, ate, nat, bat
groups: [eat, tea, ate], [tan, nat], [bat]

One way to solve this is to compare every pair of words and ask whether they are anagrams. That works, but it is slow. With 1,000 words there are about half a million pairs to check, and each check looks at the letters again. The dict approach looks at each word once.

The idea: one key for each group

Imagine that every word in a group gets stamped with the same label. If you put the labels in a dict, each label leads to a list of words. When you see a new word, you compute its label, find the list for that label, and add the word to it. If the list does not exist yet, you create it.

word "eat"  -> label "aet" -> list [eat]
word "tea"  -> label "aet" -> list [eat, tea]
word "tan"  -> label "ant" -> list [tan]
word "ate"  -> label "aet" -> list [eat, tea, ate]

The label must be the same for all anagrams and different for words that are not anagrams. Two labels work well. Both are described below.

Key one: the sorted letters

If you sort the letters of a word, every anagram gives the same result. "eat", "tea" and "ate" all sort to "aet". "tan" and "nat" both sort to "ant". The sorted letters are the key.

In Python, sorted(word) returns a new list of the letters in order. A string has no sort method, so the list is joined back into a string with "".join(...). The original word is not changed, because strings cannot be changed in Python at all.

def sorted_key(word):
    return "".join(sorted(word))

The grouping code uses defaultdict(list). When you read a key that is missing, the defaultdict creates an empty list for it. That means the code can append to the list without checking whether the key exists first. The function takes the key function as an argument, so the same grouping code works for both keys.

sorted keys:
  eat -> aet
  tea -> aet
  tan -> ant
  ate -> aet
  nat -> ant
  bat -> abt
group by sorted key: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

The three groups match the answer. Each word was sorted once, so the work grows with the total number of letters across all the words. The dict keeps its keys in the order they were first added, so the groups appear in the order their first word appeared. You do not need a special kind of dict for that, because Python dicts keep insertion order.

Watching the dict fill up

The dict changes after every word. The program below adds the words one at a time and prints the dict after each step.

after eat: {'aet': ['eat']}
after tea: {'aet': ['eat', 'tea']}
after tan: {'aet': ['eat', 'tea'], 'ant': ['tan']}
after ate: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan']}
after nat: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat']}
after bat: {'aet': ['eat', 'tea', 'ate'], 'ant': ['tan', 'nat'], 'abt': ['bat']}

Read the lines for tea and ate. The word tea has key aet, which is already in the dict, so tea is added to the list under it and no new group appears. The word tan has key ant, which is new, so a new group is made. Each word does one lookup and at most one new list, and that is the whole grouping step.

What the sorted key costs

Sorting a list of k letters takes about k times log k steps. For a word with 3 letters, that is a tiny amount of work. For a word with 1,000 letters it is more, but still far less than comparing every pair of words. The total cost for n words of length about k is about n times k times log k.

The key is also short. It is exactly as long as the word, so memory is small for normal words.

Key two: the count of each letter

The sorted key does work on every word. There is another key that avoids sorting. Count how many times each letter appears. Two words are anagrams if and only if all of their letter counts match.

For "eat", the counts are: a appears 1 time, e appears 1 time, t appears 1 time, and every other letter appears 0 times. For "tea" the counts are the same, so the two words share a key.

For lowercase English letters there are 26 possible letters, so the counts fit in a list of 26 numbers. Index 0 holds the count of a, index 1 holds the count of b, and so on. The function ord returns a character's code, so ord("c") - ord("a") is 2, because the code of a is 97 and the code of c is 99.

Python gives you two ways to turn the list into a key. The first makes a string, as the Java version does. The second uses the list as a tuple. A tuple is a fixed group of values, written with parentheses, and tuples can be dict keys because their contents cannot change. The program below builds both keys.

  eat -> 1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#
  tea -> 1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#
  tan -> 1#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#1#0#0#0#0#0#0#
  ate -> 1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#
  nat -> 1#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#1#0#0#0#0#0#0#
  bat -> 1#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#
group by count key: {'1#0#0#0#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#': ['eat', 'tea', 'ate'], '1#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#1#0#0#0#0#0#0#': ['tan', 'nat'], '1#1#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#0#1#0#0#0#0#0#0#': ['bat']}
group by tuple key: {(1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['eat', 'tea', 'ate'], (1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['tan', 'nat'], (1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0): ['bat']}

The groups are the same in both cases. The keys look different, but they do the job. Notice that eat, tea and ate have the same count key. So does tan with nat. And bat has its own key because it has a b and no n.

The string key has a separator after every count. Without it, the counts 1 and 11 would run together, and two different count sets could make the same string by accident. The # keeps each number separate. The tuple key does not need a separator at all, because each count is its own item in the tuple. That is why the tuple is the better key in Python. It can also be compared with == directly.

What the count key costs

Counting takes one pass over the word, so the work is about k steps for a word of length k. Building the key takes another 26 steps, no matter how long the word is. The total cost for n words is about n times (k + 26).

The string key has 26 numbers and 26 separators, so it is 52 characters when every count is one digit. That is longer than the sorted key for short words such as "eat". The tuple key holds 26 numbers and no separators. A count of 10 or more adds a digit to the string form, and the tuple form is not affected.

Choosing between the two keys

Both keys produce the same groups. The choice depends on what the words look like.

For a typical list of short words, both keys are fast and either is fine. The sorted key is simpler to read and to explain. The count key is the better choice when the words are long, because it does not pay the extra cost of sorting.

The mistake that breaks grouping: a list as a key

A tempting idea is to skip building a key and use the count list itself as the key. The code looks clean.

from collections import defaultdict
 
 
def count_list(word):
    counts = [0] * 26
    for ch in word:
        counts[ord(ch) - ord("a")] += 1
    return counts
 
 
groups = defaultdict(list)
for word in ["eat", "tea"]:
    groups[count_list(word)].append(word)

TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Python refuses the list at once. A dict key must be hashable, which means it has a hash value that never changes. A list can change after you add it, so Python does not allow it as a key. The error names the type, so the cause is easy to find. The fix is the tuple from the last section. A tuple is the same kind of sequence, but it cannot change, so it is hashable.

Java has a related trap. A Java array is not a value type, so two arrays with the same numbers are different keys in a HashMap. Python does not allow the list at all, so the mistake is caught early. Tuples in Python behave as values: two tuples with the same items are equal, and they find the same dict entry.

Second example: letters repeated, and empty strings

The next input has harder cases. It has words with repeated letters, a word with one letter, and empty strings. An empty string is an anagram of another empty string, because both have zero letters.

tricky group by sorted: {'abc': ['abc', 'cba', 'bca'], 'x': ['x'], 'xx': ['xx'], '': ['', '']}
tricky group by tuple: {(1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0): ['abc', 'cba', 'bca'], (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0): ['x'], (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 0, 0): ['xx'], (0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0): ['', '']}

Both keys put abc, cba and bca together. They keep x and xx apart, because one has one x and the other has two. Both keys also put the two empty strings in one group. The sorted key for the empty string is the empty string '', which is correct, because there are no letters to sort. The tuple for an empty word is 26 zeros.

The tuple for x has a 1 at index 23, because x is the 24th letter and index 23 holds its count. The tuple for xx has a 2 at the same index. That is why the position in the tuple matters: index 23 means x, and no other letter.

Third example: a longer word with the same letters

Suppose the input has listen, silent, enlist and google. The first three are anagrams. google is not, because it has two os and only one i. Walk through the sorted key for listen.

The letters of listen are l, i, s, t, e, n. Sorted alphabetically, they become e, i, l, n, s, t, which is the key eilnst. The other two anagrams also sort to eilnst. The key for google is eggloo, because its letters sort to e, g, g, l, o, o. That key is different, so google starts its own group.

The tuple key for listen has a 1 at each of e, i, l, n, s and t, and zeros everywhere else. The tuple key for google has 2 at g and at o, which differs from the listen tuple, so the two groups stay apart.

Read the key for a word once, by hand, before you rely on it. If you can write the sorted letters or the counts for a word on paper, you can predict where it will go in the dict. That habit catches many bugs early.

Common mistakes

Using a list as a dict key. This is covered above. Python raises TypeError at once. Convert the counts to a tuple, or to a string.

Sorting a string directly. A string has no sort method, because strings cannot be changed. This is the error:

word = "eat"
word.sort()

AttributeError: 'str' object has no attribute 'sort'

The fix is sorted(word), which returns a new list, and then "".join(...) to make a string from it.

Reading a missing key with square brackets. A dict raises KeyError when a key is missing. This is the error from a small test that reads "pear" from a dict that only has "apple":

prices = {"apple": 3}
print(prices["pear"])

KeyError: 'pear'

When building groups, defaultdict(list) avoids this, because it creates the missing list for you. If you use a plain dict, write groups.setdefault(key, []).append(word) or check with in first.

Forgetting that the key must match exactly. "Eat" and "eat" are different letters to Python's sort, and the count key treats an uppercase letter as a different index. If the input mixes capital and small letters, convert each word to lowercase before building the key. The count key above also assumes only a to z. A character outside that range makes ord(ch) - ord("a") fall outside the list. Some of those values raise IndexError, and others do not:

Z went to index -7 and counts[19] is 1

Python reads a negative index from the end of the list, so -7 quietly becomes slot 19, which is the slot for t. The count is wrong and no error appears. A character such as ! gives an index below -26, and that one raises IndexError: list index out of range. The fix is to lowercase the word and to reject anything that is not a letter before you count it.

Building a list of groups with a search instead of a dict. It is easy to check whether a group exists by scanning a list of groups. That makes the work grow with the number of groups every time. The dict gives the group in one step.

Practice

Each exercise has an answer below it. Try each one on paper before you read the answer.

1. What is the sorted key for listen?

Show the answer

The letters sorted are e, i, l, n, s, t, so the key is eilnst.

2. What is the first part of the count key for aab? Give the first four counts, then say how many more counts follow in the tuple.

Show the answer

The count of a is 2 and the count of b is 1, so the tuple starts (2, 1, 0, 0, ...). Then 24 more zeros follow, one for each letter from c to z, which makes 26 counts in all.

3. Given dog, god, cat, act, tac and dgo, how many groups does the sorted key make? List them.

Show the answer

There are 2 groups. dog, god and dgo all sort to dgo. cat, act and tac all sort to act.

4. A program groups ab and ba into one group with the sorted key, but a teammate says the count key will put them in two groups. Who is right?

Show the answer

The teammate is wrong. Both words have one a and one b, so the count tuple is the same for both. Anagrams always share a count key, whatever order their letters are in.

5. Why does this code raise an error? m = {} then m[[1, 2]] = "x".

Show the answer

A list can change after it is added, so Python does not allow it as a dict key. The error is TypeError: cannot use 'list' as a dict key (unhashable type: 'list'). Use a tuple instead, as in m[(1, 2)] = "x". A tuple with the same items finds the same entry.

Summary

• Give every group one shared key, so a dict can collect the words in one step each.
• The sorted letters are a key that every anagram shares, and "".join(sorted(word)) builds it.
• The letter counts are another key. Build them in a list of 26 numbers, then turn the list into a tuple.
• Never use a list as a dict key, because Python refuses it. Use a tuple, which is hashable and compares by its items.
• Choose the sorted key for short words for clarity, and the count key for long words to avoid sorting.