190. Word Ladder Length

Why this mechanism works

Words are graph vertices and legal one-letter substitutions are unweighted edges. Generate neighbors when needed instead of building all pairwise comparisons. Remove a dictionary word when enqueuing it, combining membership and undiscovered status. BFS then yields the shortest word sequence.

State and boundaries

remaining contains dictionary words not yet discovered. Queue entries pair a word with its path length in words, including begin.

Protocol

1. Handle equal endpoints and a missing end.
2. Enqueue begin at length one.
3. Replace each position by each different letter.
4. Remove and enqueue every remaining candidate.
5. Return on reaching end, or zero on exhaustion.

Visualization

hit -> hot -> dot -> dog -> cog
word counts: 1,2,3,4,5
each arrow changes exactly one letter

Python implementation

from collections import deque
from string import ascii_lowercase

def word_ladder(begin, end, words):
    if begin == end:
        return 1
    remaining = set(words)
    if end not in remaining:
        return 0
    remaining.discard(begin)
    queue = deque([(begin, 1)])
    while queue:
        word, length = queue.popleft()
        for i in range(len(word)):
            for char in ascii_lowercase:
                if char == word[i]:
                    continue
                candidate = word[:i] + char + word[i + 1:]
                if candidate not in remaining:
                    continue
                if candidate == end:
                    return length + 1
                remaining.remove(candidate)
                queue.append((candidate, length + 1))
    return 0

Worked execution

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

L5 word_ladder: if begin == end:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']

L7 word_ladder: remaining = set(words)
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}

L11 word_ladder: queue = deque([(begin, 1)])
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([('hit', 1)])

L13 word_ladder: word, length = queue.popleft()
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([]); word='hit'; length=1

L14 word_ladder: for i in range(len(word)):
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([]); word='hit'; length=1; i=0

L15 word_ladder: for char in ascii_lowercase:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([]); word='hit'; length=1; i=0; char='a'

L18 word_ladder: candidate = word[:i] + char + word[i + 1:]
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([]); word='hit'; length=1; i=0; char='a'; candidate='ait'

L15 word_ladder: for char in ascii_lowercase:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog', 'dog', 'dot', 'hot', 'log', 'lot'}; queue=deque([]); word='hit'; length=1; i=0; char='b'; candidate='ait'

... 637 intermediate state changes omitted ...

L15 word_ladder: for char in ascii_lowercase:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog'}; queue=deque([('log', 4)]); word='dog'; length=4; i=0; char='b'; candidate='aog'

L18 word_ladder: candidate = word[:i] + char + word[i + 1:]
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog'}; queue=deque([('log', 4)]); word='dog'; length=4; i=0; char='b'; candidate='bog'

L15 word_ladder: for char in ascii_lowercase:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog'}; queue=deque([('log', 4)]); word='dog'; length=4; i=0; char='c'; candidate='bog'

L18 word_ladder: candidate = word[:i] + char + word[i + 1:]
begin='hit'; end='cog'; words=['hot', 'dot', 'dog', 'lot', 'log', 'cog']; remaining={'cog'}; queue=deque([('log', 4)]); word='dog'; length=4; i=0; char='c'; candidate='cog'

L5 word_ladder: if begin == end:
begin='hit'; end='cog'; words=['hot', 'dot', 'dog']

L7 word_ladder: remaining = set(words)
begin='hit'; end='cog'; words=['hot', 'dot', 'dog']; remaining={'dog', 'dot', 'hot'}

Why the solution is correct

Every generated edge changes one character and lands in the dictionary. BFS first-discovery distances are shortest edge counts; starting at one converts them to word counts. Removing candidates at discovery prevents repeated scheduling without losing a shorter route.

Time and space

O(N*26*L^2) time in Python for up to N discovered words of length L, including slicing and hashing each candidate; O(N*L) dictionary/queue string storage.

Common mistakes

Starting the distance at zero returns transformations instead of words. Failing to remove on enqueue can greatly duplicate work across neighboring words.

Reasoning card

Transfer exercise

Use bidirectional BFS, always expanding the smaller frontier, and define how two frontier distances combine.