Lesson 45 — Graphs V: BFS on invisible graphs

~25 minutes · implicit graph BFS · Python

Tonight's problem is Word Ladder. It looks like a word puzzle: change hit into cog, one letter at a time, using only allowed words. In interviews, the trick is not vocabulary. The trick is seeing the invisible graph hiding under the words.

The invariant

First decide what a node and an edge are — here words, one letter apart — then BFS finds the shortest unweighted path.

That one sentence is the whole move. A node is a word. An edge exists when two words differ by exactly one letter. Every edge has the same cost: one transformation. In an unweighted graph, breadth-first search visits distance 1 before distance 2, distance 2 before distance 3, and so on, so the first time it reaches the target is the shortest path.

Each column is one BFS level rippling out from the start word; the first time the wave touches cog, that level is the shortest transformation length.

Word Ladder: the slow way first

Brute force is to build the hidden graph directly: compare every pair of words, connect the pairs that differ by one letter, then run BFS. If there are n words and each word has length L, the pair comparisons cost O(n²L). It works, but it spends most of its time proving that unrelated pairs are not edges.

The better approach avoids comparing every pair. For each word, create wildcard patterns. hot becomes *ot, h*t, and ho*. Words that share a pattern are one letter apart, so the pattern map becomes a cheap way to ask, “who are this word's neighbors?”

Python gives us collections.deque for queue operations from the left, and set for visited words. The LeetCode prompt asks for the number of words in the shortest transformation sequence, so the starting distance is 1, not 0.

def word_ladder(begin, end, buckets):
    q, seen = deque([(begin, 1)]), {begin}
    while q:
        word, dist = q.popleft()        # nearest word first
        if word == end: return dist
        for pat in patterns(word):      # hit -> *it, h*t, hi*
            for nxt in buckets[pat]:
                if nxt not in seen:
                    seen.add(nxt); q.append((nxt, dist + 1))
            buckets[pat] = []           # do not scan again
    return 0

Read that as a graph algorithm, not a string trick: pop one node, list its edges through the wildcard buckets, enqueue unseen neighbors at distance dist + 1. The helper patterns(word) just returns the wildcard forms for one word; buckets maps each wildcard form to the words that match it.

Transfer: same graph, new costume

Minimum Genetic Mutation: each gene string can mutate one character at a time, and every intermediate gene must exist in the bank.

Before opening the reveal: name the node, the edge, and the traversal. Do not code yet. Just state the graph.

What the trade buys you

The bucket version pays memory to avoid testing every pair. With short words, that trade is exactly what makes the invisible graph usable.

Practice — answer before you scroll past

for nxt in buckets[pat]:
    q.append((nxt, dist + 1))

Your move (tonight)

Solve Word Ladder on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode.

1. Predict: say the node, edge, brute force, and complexity out loud.
2. Attempt: build wildcard buckets, then run BFS with a queue and a visited set.
3. Compare: watch the source below only after your attempt.
4. Encode: write the invariant from the top of this page in your own words.