Word ladder with BFS and wildcard buckets

Why this matters

A word ladder is a puzzle. You start with one word and must reach another word by changing one letter at a time. Each step must produce a real word from a list you are given. The puzzle asks for the fewest steps. It is a common exercise in programming interviews, and the method behind it is useful beyond the puzzle. Any problem where you have many strings and a step means "change one piece" has the same shape. Spell-checkers that suggest close words and tools that list nearby names in a directory face similar questions.

This lesson builds the solution in three stages. First you see the graph hidden in the puzzle. Then you use breadth-first search (BFS), the search that finds the fewest steps, which you met in the lesson on representations and BFS. Last you make the search fast by grouping words into buckets, so that finding the neighbours of a word does not require checking every word in the list.

The lesson on shortest path reconstruction covers how to print the chain itself. This lesson only returns how many words the chain has.

The puzzle, step by step

Suppose you want to turn hit into cog. The word list is:

hot dot dog lot log cog

One chain that works is:

hit -> hot -> dot -> dog -> cog

Each step changes exactly one letter. hit becomes hot by changing the i to o. hot becomes dot by changing the h to d. Each word after the first one must be in the list. The first word, hit, does not need to be in the list, because it is the starting point.

The chain above has five words, counting the first and the last. The answer to the puzzle is the number of words in the chain, so the answer is 5. A chain with four words is not possible here, and the search must prove that no shorter chain exists. If no chain exists at all, the answer is 0.

Two terms are needed. A string is a piece of text, such as hot. A chain is an ordered list of words in which each word differs from the one before it by one letter.

Words as nodes

The graph view makes the puzzle easier. Each word is a node, which means one item in a graph. Two words are joined by an edge when they differ by exactly one letter. The puzzle asks for the shortest path from the start node to the target node.

Every edge counts as one step, so every edge has the same cost. A search that explores the graph level by level finds the shortest path in such a graph. This is breadth-first search. It first visits every word one step from the start, then every word two steps from the start, and so on. The first time it reaches the target, the number of steps is the smallest possible. The breadth-first search lesson gave the same argument for a graph of numbered nodes. Here the nodes are words, but the argument is the same.

Before any code, check the idea on a pair of words. hot and dot are neighbours, because they differ only in the first letter. hot and dog are not neighbours, because they differ in two places.

A direct check for one pair of words is a short loop. It compares the letters at each position and counts the differences.

bool oneLetterApart(const std::string& a, const std::string& b) {
    if (a.size() != b.size()) {
        return false;
    }
    int diff = 0;
    for (std::size_t i = 0; i < a.size(); ++i) {
        if (a[i] != b[i] && ++diff > 1) {
            return false;
        }
    }
    return diff == 1;
}

The first check returns false when the words have different lengths, because a one-letter change never changes the length. The loop stops early as soon as it finds a second difference. The && operator checks the left side first. So a[i] != b[i] is tested before the counter goes up.

A search that uses this check would, for each word it removes from the queue, compare that word with every other word in the list. For a list of N words, that is N comparisons per step. Every word in the list is removed at most once, so the work adds up to about N times N comparisons, each of which looks at up to L letters, where L is the word length. For a list of 5,000 words that is 25 million pair checks. Most of them are wasted, because most pairs of words are not neighbours. The next section removes that waste.

Wildcard buckets

A wildcard pattern is a word with one letter replaced by *. The * stands for any letter. The word hot gives three patterns:

*ot    (the first letter is a wildcard)
h*t    (the middle letter is a wildcard)
ho*    (the last letter is a wildcard)

Now look at what happens when two words share a pattern. The words hot and dot both give *ot. They match in the last two letters, and that is exactly the case where they are one letter apart. The words hot and hog both give ho*. The rule is simple. Two different words are neighbours exactly when they share at least one pattern. A word that does not share any pattern with another word is not its neighbour.

A bucket is a group of items stored under one key. Here the key is a pattern and the items are the words that produce it. This is a map from pattern to list of words, in the std::unordered_map form of the C++ standard library. A map stores key and value pairs and finds a value from its key quickly.

Take the list hot dot dog lot log cog. Building the buckets gives these rows, with one row for each pattern that has words in it.

To find the neighbours of dog, the search makes three patterns from it: *og, d*g and do*. The bucket *og holds dog, log and cog. The bucket d*g holds only dog. The bucket do* holds dot and dog. The word dog itself is already visited, so the search skips it. The new neighbours are log, cog and dot. The search never looked at hot, lot or any other word that was not in one of those three buckets.

The code that builds the buckets is short. For each word, make one pattern per letter and add the word to that pattern's bucket.

std::string pattern(std::string word, std::size_t i) {
    word[i] = '*';
    return word;
}

The function takes the word by value. It makes its own copy, so the caller's word is not changed. Writing to word[i] in a const std::string& parameter would be a compile error, and the Mistakes section shows the message.

The full solution

The program below is the complete solution. It also contains the test cases the lesson uses. A set stores each value once and can tell quickly whether a value is in it.

#include <cstddef>
#include <iostream>
#include <queue>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
 
// Replace the letter at position i with '*'.
std::string pattern(std::string word, std::size_t i) {
    word[i] = '*';
    return word;
}
 
int ladderLength(const std::string& start, const std::string& target,
                 const std::vector<std::string>& wordList) {
    const std::unordered_set<std::string> words(wordList.begin(), wordList.end());
    if (!words.contains(target)) {
        return 0;
    }
 
    std::unordered_map<std::string, std::vector<std::string>> buckets;
    for (const auto& w : wordList) {
        for (std::size_t i = 0; i < w.size(); ++i) {
            buckets[pattern(w, i)].push_back(w);
        }
    }
 
    std::unordered_set<std::string> seen{start};
    std::queue<std::pair<std::string, int>> q;  // word, number of words in the chain so far
    q.push({start, 1});
 
    while (!q.empty()) {
        auto [word, length] = q.front();
        q.pop();
        if (word == target) {
            return length;
        }
        for (std::size_t i = 0; i < word.size(); ++i) {
            auto it = buckets.find(pattern(word, i));
            if (it == buckets.end()) {
                continue;
            }
            for (const auto& next : it->second) {
                if (seen.insert(next).second) {
                    q.push({next, length + 1});
                }
            }
            it->second.clear();
        }
    }
    return 0;
}
 
int main() {
    std::cout << "hit -> cog: " << ladderLength("hit", "cog",
        {"hot", "dot", "dog", "lot", "log", "cog"}) << '\n';
    std::cout << "hit -> cog (no cog in list): " << ladderLength("hit", "cog",
        {"hot", "dot", "dog", "lot", "log"}) << '\n';
    std::cout << "a -> c: " << ladderLength("a", "c", {"a", "b", "c"}) << '\n';
    std::cout << "hot -> dot (one step): " << ladderLength("hot", "dot",
        {"hot", "dot"}) << '\n';
    std::cout << "red -> tax: " << ladderLength("red", "tax",
        {"ted", "tex", "red", "tax", "tad", "den", "rex", "pee"}) << '\n';
    return 0;
}

Compile and run it with the commands below. The -std=c++20 flag selects the C++20 rules, which the contains function on sets needs. The -Wall flag turns on the common warnings.

g++ -std=c++20 -Wall -o ladder ladder.cpp
./ladder

The output is:

hit -> cog: 5
hit -> cog (no cog in list): 0
a -> c: 2
hot -> dot (one step): 2
red -> tax: 4

The compiler printed no warnings. The g++ version used for this lesson is 15.2.0.

The first line is the example from the start of the lesson. The second line is 0 because cog is not in the list, so no chain can end on it. The third line uses a list where the answer is a chain of two words, a and c. The fourth line shows that a start word that is already in the list is not counted twice. The fifth line is a harder example, worked through in the next section.

Following the search on hit and cog

A trace shows what the search does at each step. The version below prints each word when it leaves the queue, and each bucket it reads. The only change to the program above is the printing. The search itself is the same.

pop hit (chain length 1)
  pattern h*t bucket: hot
pop hot (chain length 2)
  pattern *ot bucket: hot dot lot
  pattern ho* bucket: hot
pop dot (chain length 3)
  pattern d*t bucket: dot
  pattern do* bucket: dot dog
pop lot (chain length 3)
  pattern l*t bucket: lot
  pattern lo* bucket: lot log
pop dog (chain length 4)
  pattern *og bucket: dog log cog
  pattern d*g bucket: dog
pop log (chain length 4)
  pattern l*g bucket: log
pop cog (chain length 5)

Read the trace in the order the lines are printed. The first word, hit, has only one useful pattern, h*t, because no other word matches *it or hi*. Its bucket holds hot, so hot joins the queue with chain length 2.

The word hot is popped next. Its pattern *ot finds dot and lot, both at chain length 3. Its pattern ho* finds only hot, which has already been seen. The next word, dot, has two patterns left to check. The bucket do* finds dog, which joins the queue with chain length 4.

Some patterns are skipped without a line in the trace. The bucket h*t was already cleared when hit was popped, so hot skips it. The trace leaves out empty buckets for the same reason.

The word dog is popped with chain length 4. Its pattern *og holds log and cog. The word log was added earlier, so only cog is new. It joins the queue with chain length 5. The target is reached when cog is popped, and the function returns 5.

Note that log was added by lot, not by dog. The word lot is at chain length 3, so log gets chain length 4. The word dog is only at chain length 4, so going through dog would give log a length of 5. The queue takes words in the order they were added, so the first route found is the shortest one.

Clearing a bucket after use

The line it->second.clear(); is easy to miss, and it matters for two reasons.

The first reason is speed. Once a bucket has been read, every word in it has been added to the queue or was already seen. Reading the same bucket again would find only seen words, so the work would be wasted.

The second reason is correctness, and it is the part worth checking carefully. Clearing a bucket is safe because of the order of the BFS. The first word that reads a bucket is at the smallest chain length of any word that can reach that bucket. Every word in the bucket therefore gets the smallest chain length it can get. A later word that reads the same bucket would have a chain length that is the same or larger, so it could not give any word a shorter chain.

A harder example

The fifth case in the program is red to tax:

red -> ted -> tad -> tax

The answer is 4. The list also contains tex, rex, den and pee. None of them lies on a shortest chain. The search may read some of them, for example tex is one letter away from ted, but it stops when tax leaves the queue. The search cannot know in advance which branch is the shortest, so it has to consider the branches that do not help.

The chain has a direct step from red to ted, which is the first change. The step from ted to tad changes the middle letter. The last step from tad to tax changes the last letter. Each of the three changes uses a different position, and the buckets find each neighbour with a lookup at that position.

The cost of the buckets

The bucket approach does a fixed amount of work for each word, not for each pair of words. For a word of length L, the search makes L pattern strings and L lookups. Each lookup hashes a string of length L (turns its letters into a number that picks the slot to check), so the work for one word is about L times L character operations. Each word goes into the queue once, so the total for the search is about N times L times L, plus the work to build the buckets, which is also N times L pattern strings.

Compare this with the naive search, which compares each word with all N words, for about N times N times L character operations. The bucket version replaces a factor of N with a factor of L. For a list of 5,000 words of length 4, the naive search makes 25 million pair checks, and the bucket search does about 160,000 character operations, counting the work to build the buckets. The exact time on a real machine depends on the hashing and the memory layout, so measure it before relying on a number from this lesson.

Common mistakes

Forgetting the visited set

The seen set stops a word from joining the queue twice. Remove that check and the answer can stay correct, because the buckets are cleared after use and the search still ends. The cost is extra work. In the five test calls of the program, the version without the check pushed 44 words into the queue in total.

The check is seen.insert(next).second. The insert function returns a pair. The second value is true only when the word was new. The check and the insert happen in one step, so there is no gap in which another word could be added twice.

The check matters because a word sits in one bucket for each of its letters. With the check removed, the word can be queued once from each of those buckets.

Returning the number of changes

The puzzle asks for the number of words in the chain. The number of changes is one less. A version that returns length - 1 gives 4 for hit to cog, which is the number of steps, not the number of words. Read the question carefully and check the example: the chain hit, hot, dot, dog, cog has 5 words and 4 changes.

Using a word that is not in the list as a neighbour

A common error is to treat the starting word as a node that must be in the list. The starting word does not need to be in the list. The search above handles this because the start is put in the queue directly, and its neighbours are found by looking up its patterns. If the start word is missing from the list, its patterns simply find some words, or none.

Comparing with the wrong size

Two words of different lengths can never be one step apart. The oneLetterApart check handles this. The bucket code does not need that check, because a pattern always has the same length as its word, so a word of length 3 never shares a pattern with a word of length 4. Without the size check, oneLetterApart gives a wrong answer for cot and dots. It compares only the first three letters, which differ in one place, so it returns true, but a one-letter change cannot change the length.

A sign-compare warning

The loop for (int i = 0; i < w.size(); ++i) looks harmless, but the compiler warns about it. The size function returns an unsigned number, and int is signed. The comparison converts the signed int to an unsigned number, so a negative value would become a huge number. With -Wall, the compiler reports this for a version of the program that uses int as the loop counter:

ladder_warn.cpp: In function ‘int ladderLength(const std::string&, const std::string&, const std::vector<std::__cxx11::basic_string<char> >&)’:
ladder_warn.cpp:23:27: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   23 |         for (int i = 0; i < w.size(); ++i) {
      |                         ~~^~~~~~~~~~

The fix is to use std::size_t for the loop counter, as the program above does.

Using contains with an old standard

The contains function on sets was added in C++20. Compiling with an older standard fails with this message:

ladder.cpp: In function ‘int ladderLength(const std::string&, const std::string&, const std::vector<std::__cxx11::basic_string<char> >&)’:
ladder.cpp:19:16: error: ‘const class std::unordered_set<std::__cxx11::basic_string<char> >’ has no member named ‘contains’
   19 |     if (!words.contains(target)) {
      |                ^~~~~~~~

Compile with -std=c++20, or use words.find(target) == words.end() in older code.

Writing to a const parameter

If the helper takes the word as const std::string& and changes a letter in place, the compiler stops with an error:

constbug.cpp: In function ‘std::string pattern(const std::string&, std::size_t)’:
constbug.cpp:5:13: error: assignment of read-only location ‘(& word)->std::__cxx11::basic_string<char>::operator[](i)’
    5 |     word[i] = '*';

The compiler is right. The fix is the one in the program: take the word by value, so the function works on its own copy.

Practice

Exercise 1

List the three patterns for the word dog, and the bucket each pattern would hold for the list dog dot dig.

Show the answer

The patterns are *og, d*g and do*. The bucket for *og holds dog. The bucket for d*g holds dog and dig. The bucket for do* holds dog and dot. Of the three patterns of dog, the word dig appears only in d*g.

Exercise 2

What does ladderLength("cat", "dog", {"cot", "dot", "dog"}) return, and what does it return with the list {"cot", "dot"}?

Show the answer

The first call returns 4. The chain is cat, cot, dot, dog, which has 4 words. The second call returns 0, because dog is not in the list, so no chain can end on it. The program printed exactly these values when it was run for this lesson.

Exercise 3

Change the program so that it returns the number of changes instead of the number of words. Give the new result for hit to cog.

Show the answer

Replace return length; with return length - 1;. The result for hit to cog is 4. The chain has five words and four changes, so the answer is one less than the number of words. Be careful when the start and target are the same word: that case returns 0 under the new rule, which is correct, because no change is needed.

Exercise 4

A list has 10,000 words, and every word has 6 letters. What is the largest number of bucket keys the list can produce? Explain why the real number is usually smaller.

Show the answer

Each word gives 6 patterns, so 10,000 words give at most 60,000 patterns. The real number is usually smaller because different words often share a pattern. For example, hot and dot share *ot, so the two words use one key between them. The count is at most 60,000, and the words in the list decide the exact number.

Exercise 5

Why is it safe for the search to clear a bucket after reading it, even though a word in the bucket might be a neighbour of another word that is read later?

Show the answer

When the bucket is read for the first time, the word reading it is at the smallest chain length of any word that can reach that bucket. Each word in the bucket is therefore added with the smallest possible length. A later word that reads the same bucket can only add words with the same or a larger length. Those words are already seen, so the search would skip them anyway.

Summary

• A word ladder is a shortest-path problem on a graph where each word is a node and words one letter apart are joined by an edge.
• Breadth-first search finds the fewest steps, because it explores words in order of their distance from the start.
• A wildcard pattern replaces one letter with *, and two words share a pattern exactly when they are the same word or one letter apart.
• Buckets map each pattern to its words, so the search finds the neighbours of a word with a few lookups instead of a scan of the whole list.
• Clearing a bucket after use is safe because the first word that reads it gives every word in it the smallest possible chain length.