← Back to Python Examples

Word Ladder

BFS on an implicit graph — shortest path without any explicit edges.

Contents

  1. The Problem
  2. Thinking in Graphs
  3. The BFS Solution
  4. Trace
  5. Optimization — Bidirectional BFS

1. The Problem

Given a beginWord, an endWord, and a dictionary word list, find the length of the shortest transformation sequence from begin to end where:

# beginWord="hit", endWord="cog"
# wordList=["hot","dot","dog","lot","log","cog"]
# hit → hot → dot → dog → cog   →  5 steps
#
# beginWord="hit", endWord="cog"
# wordList=["hot","dot","dog","lot","log"]
# "cog" not in list → 0 (impossible)

2. Thinking in Graphs

Each word is a node. Two words are connected by an edge if they differ by exactly one letter. We want the shortest path from beginWord to endWord — that's BFS.

The clever part: instead of precomputing all edges, we generate neighbors on the fly by trying all 26 letters at each position.

# From "hot", try changing each character:
# _ot: aot, bot, cot, dot ← in wordList!  hot, jot, lot ← in list!
# h_t: hat, hbt, ... (only those in wordList matter)
# ho_: hoa, hob, ... (only those in wordList matter)

3. The BFS Solution

from collections import deque

def ladder_length(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set:
        return 0

    queue = deque([(beginWord, 1)])  # (current_word, steps_taken)
    visited = {beginWord}

    while queue:
        word, steps = queue.popleft()
        for i in range(len(word)):
            for ch in 'abcdefghijklmnopqrstuvwxyz':
                next_word = word[:i] + ch + word[i+1:]
                if next_word == endWord:
                    return steps + 1
                if next_word in word_set and next_word not in visited:
                    visited.add(next_word)
                    queue.append((next_word, steps + 1))

    return 0  # No path found

print(ladder_length("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  # 5
PropertyValue
TimeO(M² × N) where M = word length, N = number of words
SpaceO(M × N) for the queue and visited set
Converting wordList to a set is critical. Checking membership in a list is O(n); in a set it's O(1). For a large dictionary this makes an enormous difference.

4. Trace

# Start: queue=[("hit",1)], visited={"hit"}
#
# Pop ("hit",1).  Try all 1-letter changes:
#   "hot" → in word_set, not visited → enqueue ("hot",2)
# queue=[("hot",2)]
#
# Pop ("hot",2).  Try all changes:
#   "dot" → enqueue ("dot",3)
#   "lot" → enqueue ("lot",3)
# queue=[("dot",3),("lot",3)]
#
# Pop ("dot",3).
#   "dog" → enqueue ("dog",4)
#
# Pop ("lot",3).
#   "log" → enqueue ("log",4)
#
# Pop ("dog",4).
#   "cog" == endWord! Return 4+1 = 5  ✓

5. Optimization — Bidirectional BFS

Search from both ends simultaneously. When the two frontiers meet, add their step counts. This dramatically reduces the search space — instead of exploring a sphere of radius d, you explore two spheres of radius d/2, which is much smaller.

def ladder_length_bidir(beginWord, endWord, wordList):
    word_set = set(wordList)
    if endWord not in word_set: return 0

    front, back = {beginWord}, {endWord}
    visited = {beginWord, endWord}
    steps = 1

    while front:
        if len(front) > len(back):
            front, back = back, front  # Always expand the smaller frontier
        next_front = set()
        for word in front:
            for i in range(len(word)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + ch + word[i+1:]
                    if nw in back: return steps + 1
                    if nw in word_set and nw not in visited:
                        next_front.add(nw)
                        visited.add(nw)
        front = next_front
        steps += 1
    return 0
Bidirectional BFS can reduce time from O(b^d) to O(b^(d/2)) where b=branching factor, d=depth. In practice this is often a 100x speedup for long paths.