Word Ladder: BFS on a Graph You Never Build

Many shortest-path questions never mention a graph. "Change one letter at a time to turn cold into warm." "Turn the wheels of a combination lock from 0000 to a target while avoiding certain codes." "Reach this puzzle position in as few moves as possible." Each one is breadth-first search in disguise, and the disguise is that nobody gives you the edges. You generate them from a rule, one state at a time, and only for the states the search actually reaches.

The problem it solves

In a textbook graph problem you receive an adjacency list. In an implicit graph you receive a start state, a goal, and a rule for which states follow a given state. The graph exists only in principle: the set of all four-letter strings has 26 to the fourth power, 456,976 members, and a puzzle's state space can be far larger. Building all of it first would waste time and memory on states the search never needs.

The question is the same one BFS answers on any unweighted graph: what is the fewest number of moves from start to goal? For a word ladder, each move changes one letter, and every intermediate word must be in the dictionary.

The intuition

BFS needs only two things from a graph: a way to list the neighbours of the node it just popped, and a way to remember which nodes it has already seen. Neither requires the edges to be stored.

• Neighbours on demand. For a word, try every position and every letter. A four-letter word gives 4 × 26 = 104 candidate strings. Keep only the ones in the dictionary. That check is the edge.
• The seen set is still mandatory. The generator happily re-creates states you already left: cord is one letter from cold, and cold is one letter from cord. Without a seen set, the queue fills with repeats.
• Mark on enqueue, not on dequeue. Adding a state to the seen set when you push it means each state enters the queue at most once.

Because every move costs the same, the first time BFS pops the goal it has found a shortest route, exactly as in shortest path in an unweighted graph. To report the route itself rather than its length, store each state's parent when you first see it and walk the parents back from the goal.

Watch it run

The animation's dictionary is cold, cord, card, ward, warm and wolf. Nothing is stored but that set; there is no adjacency list, because the neighbours are invented on demand. It pops cold and builds every one-letter change: 4 × 26 = 104 candidate strings, almost all of them nonsense. Exactly one candidate is in the set, cord. That is an edge, created now, used now, never stored. The same happens for cord, which yields card, then card, which yields ward, and ward, which yields warm. When warm pops off the queue, the search stops: 5 words and four edits, on a graph that was never built. The last frame points at wolf. It is in the dictionary but was never even generated, because no explored word is one letter away from it. Unreached states cost nothing.

The code

The lesson's loop, counting words on the ladder, so the answer is 5 for four edits:

from collections import deque
words = {"cold", "cord", "card", "ward", "warm", "wolf"}

q = deque([("cold", 1)])
seen = {"cold"}
steps = 0
while q:
    word, d = q.popleft()
    if word == "warm":
        steps = d
        break
    for i in range(len(word)):                       # neighbours are computed,
        for ch in "abcdefghijklmnopqrstuvwxyz":      # never stored
            nxt = word[:i] + ch + word[i + 1:]
            if nxt in words and nxt not in seen:
                seen.add(nxt)
                q.append((nxt, d + 1))

print(steps)   # 5: cold, cord, card, ward, warm

Pulling the rule out into a neighbours function gives one BFS that works for any implicit graph. The parent dictionary doubles as the seen set and gives back the path:

def bfs(start, goal, neighbours):
    """Fewest moves from start to goal; neighbours(state) yields next states."""
    parent = {start: None}
    q = deque([start])
    while q:
        state = q.popleft()
        if state == goal:
            path = []
            while state is not None:
                path.append(state)
                state = parent[state]
            return path[::-1]
        for nxt in neighbours(state):
            if nxt not in parent:                    # parent doubles as the seen set
                parent[nxt] = state
                q.append(nxt)
    return None

def one_letter_edits(dictionary):
    def neighbours(word):
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i + 1:]
                if nxt != word and nxt in dictionary:
                    yield nxt
    return neighbours

print(bfs("cold", "warm", one_letter_edits(words)))
# ['cold', 'cord', 'card', 'ward', 'warm']
print(bfs("cold", "wolf", one_letter_edits(words)))   # None

The same function solves a combination lock. Each of four wheels turns one step either way, wrapping from 9 to 0, and some codes jam the lock. The direct three-turn routes are all blocked, so the answer takes five turns:

def lock_moves(dead):
    def neighbours(code):
        for i in range(4):
            d = int(code[i])
            for turn in (1, -1):                     # each wheel turns either way
                nxt = code[:i] + str((d + turn) % 10) + code[i + 1:]
                if nxt not in dead:
                    yield nxt
    return neighbours

path = bfs("0000", "0120", lock_moves({"0100", "0020", "0110", "9120"}))
print(len(path) - 1, path)
# 5 ['0000', '1000', '1100', '1110', '1120', '0120']

The brute force builds the graph explicitly, by comparing every pair of words, and runs BFS on stored edges. On 400 random dictionaries, the implicit search must reach the same words at the same distances, and every returned path must be a real shortest path:

import random, string

def explicit_graph(dictionary):
    # brute force: compare every pair of words and store the edges
    adj = {w: [] for w in dictionary}
    for a in dictionary:
        for b in dictionary:
            if sum(x != y for x, y in zip(a, b)) == 1:
                adj[a].append(b)
    return adj

def distances(start, neighbours):
    dist, q = {start: 0}, deque([start])
    while q:
        s = q.popleft()
        for t in neighbours(s):
            if t not in dist:
                dist[t] = dist[s] + 1
                q.append(t)
    return dist

random.seed(22)
ok = True
for _ in range(400):
    letters = string.ascii_lowercase[:random.randint(2, 4)]
    dictionary = {"".join(random.choice(letters) for _ in range(3))
                  for _ in range(random.randint(1, 30))}
    start = random.choice(sorted(dictionary))
    adj = explicit_graph(dictionary)
    want = distances(start, adj.__getitem__)
    ok &= distances(start, one_letter_edits(dictionary)) == want
    goal = random.choice(sorted(dictionary))
    path = bfs(start, goal, one_letter_edits(dictionary))
    if path is None:
        ok &= goal not in want
    else:
        ok &= len(path) - 1 == want[goal]
        ok &= all(b in adj[a] for a, b in zip(path, path[1:]))
print(ok)                                            # True

The complexity

For a dictionary of N words of length L:

• Neighbour generation: each popped word builds 26 · L candidates, and each candidate costs O(L) to create and hash, so O(26 · L²) per word.
• Whole search: O(N · 26 · L²) time in the worst case, and O(N · L) space for the queue and seen set.
• The explicit alternative: comparing all pairs is O(N² · L) before the search even starts, which is why generating neighbours wins for large dictionaries. A common speed-up groups words by wildcard patterns such as c*ld, so neighbours are looked up rather than generated.

Where it goes wrong

• Marking visited on dequeue. The same word can be queued many times before it is popped, which multiplies the work.
• Using depth-first search. DFS finds a route, not the shortest one.
• Forgetting that the start may not be in the dictionary. In the usual statement only the target must be; the start is just where the queue begins.
• Counting edges when the question counts words. The ladder cold to warm has five words and four changes. Read which one is asked for.

When it shows up in interviews

Word ladder is a standard hard question and the lock with dead codes a standard medium; puzzle boards such as sliding tiles are the same search with a different neighbour rule. The skill being tested is recognising that the states form a graph at all. The step after that is multi-source BFS, where several starts enter the queue together, and the grid version of generated neighbours is number of islands. The patterns cheat sheet groups these under BFS.

How to say it in an interview

"The states form an unweighted graph, so the shortest sequence of moves is a BFS. I do not build the graph: when I pop a word I generate its neighbours by changing each position to each letter, and keep the ones in the dictionary. I mark words as seen when I enqueue them, so each is processed once, and I store a parent for each word so I can rebuild the path. The first time the target comes off the queue, its distance is the answer. That is O(N · 26 · L²) time and O(N · L) space, and states the search never reaches cost nothing."