Word Ladder: BFS Over an Implicit Word Graph

"Word Ladder" shows up again and again in Amazon, Google, LinkedIn phone screens. It is a Hard problem on paper, but the real test is whether you recognize the Tree BFS pattern quickly and code it cleanly. Part 11 of 11 in the Tree BFS arc.

The Problem

Given begin_word, end_word, and a word list, return the number of words in the shortest transformation sequence where each step changes one letter and every intermediate word is in the list; 0 if impossible. The graph is implicit — and building it wrong is the difference between passing and timing out.

Input:  begin = "hit", end = "cog", list = ["hot","dot","dog","lot","log","cog"]
Output: 5
hit -> hot -> dot -> dog -> cog

Recognizing the Tree BFS Pattern

Breadth-first search explores a tree or graph level by level using a queue, and its defining superpower is the level snapshot: freeze the queue length, process exactly that many nodes, and you have processed one complete level. Anything phrased per-level — level lists, level averages, rightmost visible node, shortest path in unweighted structures — is BFS by construction.

Minimum number of steps through discrete states is BFS on a state graph. The pattern-level lesson is edge generation: pairwise word comparison costs O(n²·L); wildcard buckets (h*t matches hot and hit) precompute neighbors in O(n·L) — the pivot from traversal problem to representation problem.

The Approach

Preprocess every list word into its L wildcard forms, bucketing words by form. BFS from the begin word: for each popped word, its neighbors are the union of its wildcard buckets; visit each word once. Distance at pop of the end word is the answer.

Clear a bucket after first use — its members are all now visited or in-queue, and re-scanning buckets is the hidden quadratic that kills large inputs. Bidirectional BFS roughly square-roots the frontier and is the expected senior-level mention.

Python Solution

from collections import defaultdict, deque


def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    """Words in the shortest one-letter-change sequence, else 0."""
    words = set(word_list)
    if end_word not in words:
        return 0
    L = len(begin_word)

    buckets: dict[str, list[str]] = defaultdict(list)
    for w in words:
        for i in range(L):
            buckets[w[:i] + "*" + w[i + 1:]].append(w)

    queue: deque[tuple[str, int]] = deque([(begin_word, 1)])
    visited = {begin_word}
    while queue:
        word, dist = queue.popleft()
        if word == end_word:
            return dist
        for i in range(L):
            key = word[:i] + "*" + word[i + 1:]
            for neighbor in buckets[key]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, dist + 1))
            buckets[key] = []               # bucket exhausted
    return 0

Complexity

• Time: O(n·L²) — n words times L wildcard forms, each form of length L for hashing
• Space: O(n·L) — buckets store each word L times

Interview Tips and Follow-Ups

• The end word must be in the list; the begin word need not be — a spec detail that flips test outcomes and shows careful reading.
• Word Ladder II (return all shortest sequences) needs BFS layering plus backtracking reconstruction — an order of magnitude more code; scope it before agreeing.
• Bidirectional BFS: always expand the smaller frontier; meeting in the middle turns b^d into 2·b^(d/2). Have the numbers ready.

That wraps part 11 of the Tree BFS arc. The full Technical Interview category maps all one hundred questions to the nine patterns that dominate FAANG screens — work through an arc end to end and the next unseen variant will feel familiar.