Word ladder with BFS and wildcard buckets in Python

Why this matters

A word ladder is a word puzzle. You start with one word, such as hit, and you want to reach another word, such as cog. Each step changes exactly one letter, and every word in the chain must be a real word from a list you are given. The goal is the chain with the fewest words.

The puzzle is a graph problem in disguise. Each word is a vertex (a point in a graph). Two words are joined by an edge when they differ by exactly one letter. Breadth-first search (BFS, from the earlier graph lessons in this module) finds the shortest path in a graph where every edge counts the same, so it finds the shortest word chain too.

The search itself is short. The slow part is finding neighbours, meaning the words one letter away from the current word. A simple approach checks every word in the list each time. With a list of 10,000 words, that is up to 10,000 checks for every word you visit. Wildcard buckets solve this. They group words by a pattern with one letter replaced by a star, so the neighbours of a word can be found with a few lookups.

Words used in this lesson

• Vertex: a point in a graph. Here, one word.
• Edge: a link between two vertices. Here, two words that differ in exactly one position.
• Neighbour: a vertex joined to another vertex by one edge.
• Chain: a list of words where each word is a neighbour of the word before it.
• Wildcard: a placeholder that stands for any letter. This lesson uses the star character *.
• Bucket: the list of words that share one pattern. For example, the bucket for *og holds dog, log and cog.
• Dict: Python's key-value store, written with curly braces. It finds a value from its key quickly. Here the key is a pattern and the value is its bucket.
• Set: an unordered collection that holds each value once. This lesson avoids sets for one reason, explained in the first program.
• Queue: a line where items leave in the order they arrived. BFS uses a queue. Python's collections.deque is the queue here.

The puzzle in plain words

Take this word list: hot, dot, dog, lot, log, cog. The start word is hit, which is not in the list. The end word is cog, which is in the list. This lesson requires the end word to be in the list, because the chain must finish on a real word. The start word does not need to be in the list.

One chain from hit to cog is:

hit, hot, lot, log, cog

Check each step. hit to hot changes the i to an o. hot to lot changes the h to an l. lot to log changes the t to a g. log to cog changes the l to a c. Every step changes one letter, and the chain has five words. Five words means four changes.

Another chain with five words is hit, hot, dot, dog, cog. When two chains have the same length, either one is a correct answer. The question asks for the length, and the first program returns the number of words, which is 5.

Why plain search is slow

Before the bucket idea, here is the simple approach. Start with hit in a queue. Take the first word off the queue. Look at every word in the list and check whether it differs from the current word by exactly one letter. If it does, and you have not seen it yet, add it to the back of the queue. Repeat until the end word comes off the queue.

This works, but every visited word triggers a full scan of the list. If the list has n words and the search visits most of them, the total work is about n times n. For 10,000 words, that is 100 million comparisons. Most of those comparisons are wasted, because most words are nowhere near the current word.

A naive version finds each word's neighbours by comparing the word with every word in the list. Each word it takes off the queue before the end word makes one comparison per word in the list. On the hit to cog puzzle, six words come off the queue before cog, and the list plus hit has seven words. That is 6 times 7, or 42 comparisons. The naive version still returns 5.

The count of 42 is small only because the list has six words. The count grows with the square of the list size.

Wildcard buckets

A wildcard bucket is built from a pattern. To make the patterns for a word, replace one letter at a time with *. The word hot gives three patterns:

• replace the first letter: *ot
• replace the middle letter: h*t
• replace the last letter: ho*

Now group every word in the list by all of its patterns. Each pattern gets one bucket, and the bucket holds every word that matches it. Calling build_buckets on the words hit, hot, dot, dog, lot, log and cog, and printing a few of the buckets, gives:

*og -> ['dog', 'log', 'cog']
*ot -> ['hot', 'dot', 'lot']
ho* -> ['hot']
l*g -> ['log']
l*t -> ['lot']
lo* -> ['lot', 'log']

The idea is simple. Two words are neighbours exactly when they share a bucket. If two words differ only in position i, then replacing position i with * gives the same pattern for both. So to find the neighbours of hot, you look up its three patterns and read the buckets.

For hot, the buckets are:

• *ot holds hot, dot and lot. Neighbours: dot and lot.
• h*t holds hit and hot. Neighbour: hit.
• ho* holds only hot. No neighbours.

The word hot shows up in its own buckets. That is harmless. The search has already seen it, so it is skipped.

Each lookup costs about the same no matter how long the list is, because a dict finds a bucket by its key. A word of length L has L patterns, so finding all neighbours of one word costs about L lookups plus the words in those buckets.

The first full program

The program below has three parts. build_buckets makes the pattern dict. ladder_length runs BFS over the buckets and returns the number of words in the shortest chain. The last block runs four small cases.

Save it as word_ladder.py and run it with python3 word_ladder.py. The output is:

hit -> cog: 5
hit -> cog (no cog in list): 0
hot -> cog: 4
same word: 1

Here is how the code works, step by step.

defaultdict(list) is a dict that makes an empty list the first time you use a new key. So buckets[pattern].append(word) works even when the pattern is new. Without it, you would check for a missing key by hand each time.

The unique_words function uses dict.fromkeys. A Python set would also remove duplicates, but a set of strings can come out in a different order from one run to the next. Python changes how it hashes strings for each run, and the order of a set depends on those hashes. A different order can give a different shortest chain. A dict keeps the order the words were given, so the output stays the same from run to run.

The steps dict stores the number of words in the chain from begin to each word the search has reached. The start word gets 1, because the chain that contains only the start word has one word. Each word queued from a word with count c gets c + 1.

The queue is first in, first out. popleft() takes the oldest word, and append() adds to the back. BFS takes words in the order they were added. Because of that order, the first time a word is added to steps, the count stored is the smallest count that word can have. The search never needs to update a count later.

The line buckets.pop(pattern, None) deserves a closer look. It removes the bucket from the dict and returns it. If the pattern is not there, it returns None instead of raising an error. The first word that uses a bucket is the one closest to the start among all words that will ever use it. Every word in that bucket is one change away from that word, so each gets a count at most one higher. A later word that uses the same bucket is at least as far from the start, so its neighbours in that bucket would get counts that are no smaller than the ones already stored. Removing the bucket skips work that cannot change any answer.

The check if current == end runs when the word comes off the queue, not when it is added. That is the standard BFS rule. It guarantees the count returned is the smallest one, because every shorter chain has already been processed.

Printing the chain itself

The count tells you how many words are in the chain. Often you also want the words. To print the chain, store a parent for each word: the word that added it to the queue. Then start at the end word and follow the parents back to the start.

The chain version uses the same search. It adds a dict called parent beside steps, and in the loop that queues a word it also sets parent[nxt] = current. When end comes off the queue, it builds the answer:

def ladder_chain(begin, end, word_list):
    # Returns the words of one shortest chain, or [] if there is none.
    words = unique_words(begin, word_list)
    if end not in words:
        return []
    buckets = build_buckets(words)
 
    steps = {begin: 1}
    parent = {}
    queue = deque([begin])
    while queue:
        current = queue.popleft()
        if current == end:
            chain = []
            w = end
            while w is not None:
                chain.append(w)
                w = parent.get(w)
            return chain[::-1]
        for i in range(len(current)):
            pattern = current[:i] + "*" + current[i + 1:]
            bucket = buckets.pop(pattern, None)
            if bucket is None:
                continue
            for nxt in bucket:
                if nxt not in steps:
                    steps[nxt] = steps[current] + 1
                    parent[nxt] = current
                    queue.append(nxt)
    return []

The loop that builds the answer collects end, then its parent, then the parent of that, until it reaches the start word. The start word has no parent, so parent.get(w) returns None and the loop stops. The list is in reverse order. The slice chain[::-1] returns a copy of the list read backwards, which flips it.

Running the chain version on the same puzzle gives:

chain: ['hit', 'hot', 'dot', 'dog', 'cog']
chain when end missing: []

The chain has five words, like the chain in the puzzle section, but it goes through dot instead of lot. The bucket *ot holds hot, dot and lot in the order the words were given, so dot is reached first. Both chains are correct. The second line is the case where the end word is not in the list. The function returns an empty list.

A larger example

The first example has six words. The next one uses a grid of 27 four-letter words. Each word has the form abcx, where a, b and c are each one of a, b or c. The final letter is always x. The start word is aaax and the end word is cccx. Those words differ in all three of their first positions, so the shortest chain must change each of those three letters at least once.

The grid is built with itertools.product, which makes every combination of the letters. The helper below compares two words and returns True only when they differ in exactly one position. The naive_ladder function uses it. It is the slow method from the earlier section, and it counts how many comparisons it makes.

def differs_by_one(a, b):
    if len(a) != len(b):
        return False
    return sum(x != y for x, y in zip(a, b)) == 1
 
 
def naive_ladder(begin, end, word_list):
    # Same search, but each visited word is compared with every word in the list.
    words = list(unique_words(begin, word_list))
    steps = {begin: 1}
    queue = deque([begin])
    comparisons = 0
    while queue:
        current = queue.popleft()
        if current == end:
            return steps[current], comparisons
        for nxt in words:
            comparisons += 1
            if nxt not in steps and differs_by_one(current, nxt):
                steps[nxt] = steps[current] + 1
                queue.append(nxt)
    return 0, comparisons
 
 
from itertools import product
 
grid = ["".join(p) + "x" for p in product("abc", repeat=3)]
print("grid words:", len(grid))
print("fast from aaax to cccx:", ladder_length("aaax", "cccx", grid))
fast_count, comparisons = naive_ladder("aaax", "cccx", grid)
print("  naive comparisons:", comparisons)
print("naive from aaax to cccx:", fast_count)
print("chain:", ladder_chain("aaax", "cccx", grid))

This block uses the functions from the first program and the chain version, so put all of them in one file before you run it. Running it prints:

grid words: 27
fast from aaax to cccx: 4
  naive comparisons: 702
naive from aaax to cccx: 4
chain: ['aaax', 'caax', 'ccax', 'cccx']

The chain changes the first letter, then the second, then the third. It has four words and three changes. The fast and naive methods agree on the length, which is a useful check when you change the code. Here 26 words come off the queue before cccx, and each is compared with all 27 words, so the naive method made 26 times 27, which is 702 comparisons. The bucket version does not scan the list for each word it visits.

A last check covers the case where the end word cannot be reached. The words ab and zz are both in the list, but no chain links aa to zz through the list, because ab and zz differ in two positions.

print("no path aa->zz:", ladder_length("aa", "zz", ["ab", "zz"]))

no path aa->zz: 0

The method returns 0 in this case. This is the same value it returns when the end word is missing from the list, so a caller that needs to tell those two cases apart must check the list first.

Common mistakes

Counting changes instead of words

The question asks for the number of words in the chain, which is one more than the number of changes. For hit to cog, the chain has five words and four changes. The program above returns 5.

A common change is to return the number of changes by mistake. If you subtract one from the result, you get 4 for the hit to cog puzzle. That is the number of changes, not the number of words. The fix is to start the counter at 1 for the start word, as the code does with steps = {begin: 1}.

Missing None check after a bucket lookup

A dict lookup with get returns None when the key is missing. If the code then loops over that None, Python raises an error. This program shows the error:

from collections import defaultdict
 
 
def build_buckets(words):
    buckets = defaultdict(list)
    for word in words:
        for i in range(len(word)):
            pattern = word[:i] + "*" + word[i + 1:]
            buckets[pattern].append(word)
    return buckets
 
 
def no_none_check(buckets, pattern):
    bucket = buckets.get(pattern)
    for next_word in bucket:
        print("neighbour", next_word)
 
 
if __name__ == "__main__":
    buckets = build_buckets(["hot", "dot", "dog"])
    print("hot is in bucket h*t:", buckets.get("h*t"))
    print("pattern z*z is in buckets:", "z*z" in buckets)
    no_none_check(buckets, "z*z")

Running it prints the following:

hot is in bucket h*t: ['hot']
pattern z*z is in buckets: False
Traceback (most recent call last):
  File "bucket_lookup.py", line 23, in <module>
    no_none_check(buckets, "z*z")
    ~~~~~~~~~~~~~^^^^^^^^^^^^^^^^
  File "bucket_lookup.py", line 15, in no_none_check
    for next_word in bucket:
                     ^^^^^^
TypeError: 'NoneType' object is not iterable

The first part of the path before the file name depends on where you save the file, so it is shortened here. The last line names the problem: a for loop was given None, which is not a list. The line above it, line 15, is the loop that failed.

The defaultdict does not raise this error, but it has its own trap. Reading a missing key creates it, so the dict changes just by being read. This snippet uses build_buckets from the program above:

buckets = build_buckets(["hot", "dot", "dog"])
print(buckets["z*z"], "z*z" in buckets)

It prints:

[] True

The read added an empty bucket for z*z. Use get when you only want to look, and [] when you want the key to be created.

The fix in the word-ladder program is buckets.pop(pattern, None) followed by if bucket is None: continue. That skips any pattern with no bucket.

Searching the list instead of the buckets

It is tempting to loop over the whole word list to find neighbours, or to test each word with in. That brings back the slow search from earlier. The bucket dict is built once, before the search starts, so each lookup stays cheap. Build the dict first, then search.

Marking words as seen too late

BFS must record a word as seen when it is added to the queue, not when it is taken off. If you wait until the word is taken off, the same word can be added to the queue several times before its first copy is processed. The answer stays correct, but the queue does more work. The code above records the count in steps at the moment it adds the word, which prevents that.

Practice

Each exercise is followed by its answer. Try each one on paper before you read the answer.

Exercise 1

Start with dot. End with cog. The word list is dot, dog, cog. How many words are in the shortest chain?

Show the answer

The chain is dot, dog, cog. dot to dog changes the t to a g. dog to cog changes the d to a c. The answer is 3. The program prints 3 for this input.

Exercise 2

List the four patterns of the word cold.

Show the answer

The patterns are *old, c*ld, co*d and col*. That is one pattern for each of the four letters.

Exercise 3

Start with a. End with c. The word list is b and c. Then the same start and end with the list b only. What does the program return in each case?

Show the answer

With the list b and c, the answer is 2. The chain is a, c, because a and c differ in one letter. With the list b only, the end word c is not in the list, so the answer is 0.

Exercise 4

Start with cat and end with dog. The word list is cot, dot, dog, cog. Find the shortest chain and say how many words it has.

Show the answer

One shortest chain is cat, cot, dot, dog. It has 4 words and 3 changes. The chain cat, cot, cog, dog also has 4 words and is also valid, because each step changes one letter. Either chain is a correct answer. The program returns 4 for this input, and ladder_chain returns ['cat', 'cot', 'dot', 'dog'].

Exercise 5

The method removes each bucket from the dict the first time a word uses it. Explain why this cannot make the answer wrong.

Show the answer

The first word that uses a bucket is the closest one to the start among all words that will ever use that bucket. Every word in the bucket is one change from that word, so each gets a count no more than one higher. A later word that uses the same bucket is at least as far from the start, so it could only give those words a count that is the same or larger. Those words already have counts that are no larger, so removing the bucket skips no useful work.

Summary

• A word ladder is a shortest path problem on a graph where each word is a vertex and one-letter changes are the edges.
• BFS finds the shortest chain because it visits words in order of their distance from the start.
• A wildcard bucket is the list of words that match one pattern with one letter replaced by *. Two words are neighbours exactly when they share a bucket.
• The method returns the number of words in the chain, not the number of changes.
• Remove a bucket after its first use with pop. This keeps the search fast without changing the answer.
• Check for None after every lookup that can miss, and record a word as seen when it is queued.