Word Ladder — The Password Drift

Boss 13: The Password Drift

Twelve bosses, and every single one handed you the graph. A grid with neighbors baked in, a course list with prerequisite arrows, a cable log with explicit pairs. The finale hands you a dictionary and nothing else, and dares you to see the graph inside it. There is no edge list. There never will be one. The edges exist only because you declare a rule for them, and that idea, the implicit graph, is the one this boss installs, along with the engineering trick that makes it fast: wildcard buckets.

The story

A legacy system has a password recovery mode from another era. You can "drift" from any word to another by changing exactly one letter, but the system validates every intermediate step against its approved word list. Real words only, all the way down.

The lost password is cog. Your last known good word is hit. The approved list: hot, dot, dog, lot, log, cog.

Play it out:

hit → hot     change i to o     (hot is approved)
hot → dot     change h to d     (dot is approved)
dot → dog     change t to g     (dog is approved)
dog → cog     change d to c     (cog is approved. In.)

chain: hit, hot, dot, dog, cog   →  5 words

There's a rival route through lot and log, also 5 words. But try to shortcut hit straight toward cog and every intermediate you invent (hig? cit?) bounces off the list. And if cog weren't on the approved list at all, no chain could ever end there: answer 0.

The question the system is really asking: fewest words from start to target, counting both ends. Fewest steps through a network of allowed states. That's a shortest path. Which means somewhere in here, there's a graph.

The problem, dressed up properly

A transformation sequence from beginWord to endWord using a dictionary wordList is a sequence of words where every adjacent pair differs by a single letter, and every word except beginWord must be in wordList. Return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.

LeetCode 127.

The naive attempt

Fine, you think, I'll build the graph the honest way: compare every pair of words, connect the ones that differ by one letter, then BFS.

def differs_by_one(w1, w2):
    return sum(a != b for a, b in zip(w1, w2)) == 1
 
def build_edges(words):
    adj = {w: [] for w in words}
    for i, a in enumerate(words):           # every pair: N² comparisons
        for b in words[i + 1:]:
            if differs_by_one(a, b):        # each costs L character checks
                adj[a].append(b)
                adj[b].append(a)
    return adj

The BFS afterward is fine. The build is the crime: O(N² · L). At LeetCode's limits, 5000 words of length 10, that's 25 million pairs and a quarter billion character comparisons, all to discover edges, most of which BFS will never even walk. You paid to materialize the whole graph when BFS only ever asks one question: who are the neighbors of the word I'm standing on right now?

The weapon: wildcard buckets and BFS

Answer the neighbor question directly. Take hot and knock out one letter at a time: *ot, h*t, ho*. Every word matching *ot differs from hot in only the first letter, which is exactly the drift rule. So group the whole dictionary by these wildcard patterns, once, up front:

*ot → hot, dot, lot        h*t → hot        ho* → hot
*og → dog, log, cog        d*t → dot        ...

Now the neighbors of any word are just the contents of its L buckets, found in O(L) lookups instead of a scan of the whole list. The graph is never built. Each node discovers its edges the moment BFS arrives, and BFS, expanding level by level, guarantees the first time it touches cog is via a shortest ladder. Unweighted graph, so BFS levels are distances, the same law Boss 4 and Boss 5 ran on grids, now running on a dictionary.

from collections import defaultdict, deque
 
def ladder_length(begin_word: str, end_word: str, word_list: list[str]) -> int:
    if end_word not in word_list:
        return 0                              # no legal chain can end there
    L = len(begin_word)
 
    buckets = defaultdict(list)               # "h*t" -> [hot, ...], built ONCE
    for word in word_list:
        for i in range(L):
            buckets[word[:i] + "*" + word[i + 1:]].append(word)
 
    queue = deque([(begin_word, 1)])          # (word, ladder length so far)
    visited = {begin_word}                    # mark on push, not on pop
    while queue:
        word, steps = queue.popleft()
        if word == end_word:
            return steps                      # BFS: first arrival is shortest
        for i in range(L):
            for neighbor in buckets[word[:i] + "*" + word[i + 1:]]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, steps + 1))
    return 0                                  # dictionary exhausted, no route

Note begin_word never needs to be in the list: its buckets are looked up, not stored, and lookups against list-built buckets are exactly what the rules allow.

Watching it work

Start hit, target cog, the list from the story:

pop (hit, 1):  buckets *it, hi* empty. h*t → hot.        visit hot, push (hot, 2)
pop (hot, 2):  *ot → dot, lot. h*t, ho* spent.           push (dot, 3) (lot, 3)
pop (dot, 3):  do* → dog.                                push (dog, 4)
pop (lot, 3):  lo* → log.                                push (log, 4)
pop (dog, 4):  *og → cog (dog, log visited).             push (cog, 5)
pop (log, 4):  *og all visited now.
pop (cog, 5):  cog == end_word → return 5 ✓

Level by level, exactly the diagram. lot and log got explored too, BFS doesn't know in advance which branch wins, but the moment any branch reaches cog, the level number is the answer and no longer route can beat it.

Gotchas

1. Not checking the target is in the list. end_word missing means no chain can legally finish, return 0 before building anything. Skip the check and BFS just burns the whole dictionary to discover it.

2. Marking visited on pop instead of on push. A word at distance 3 can be pushed by many distance-2 words before it's ever popped. Mark at push time and each word enters the queue once. Mark at pop time and dense dictionaries flood the queue with duplicates.

3. Counting changes instead of words. The contract wants the ladder length, both ends included: hit to cog is 4 changes but 5 words. Start the counter at 1, not 0. This off-by-one fails the very first test case, which is merciful.

4. Building the full adjacency list anyway. The pairwise O(N² · L) build is the trap the buckets exist to kill. Buckets cost O(N · L) inserts and answer every neighbor query for the rest of the run.

5. Reaching for DFS. DFS finds a ladder, then another, then another, and you'd have to try them all to know which is shortest. Unweighted shortest path is BFS territory, full stop. It's the last time this dungeon will say it, so say it back once.

Complexity

Each of N words spawns L patterns, and each pattern key costs O(L) to slice: buckets build in O(N · L²), and BFS visits each word once, regenerating its L patterns the same way.

Time: O(N · L²). Space: O(N · L²).

Boss down. DUNGEON DOWN. XP gained.

The screen accepts cog on the fifth word, the legacy system grumbles open, and the dictionary that looked like a flat list of strings was a graph the entire time. It just needed someone to see the edges.

What you walked away with:

• Implicit graphs: nodes plus a move rule, edges invented on arrival, never materialized
• BFS levels are distances in unweighted graphs, on grids, on dictionaries, on anything
• Wildcard buckets: precompute neighbor groups once, then O(L) lookups instead of full scans
• Visited discipline: mark on push, and every state enters the queue exactly once

The full haul from Dungeon 11:

• Flood fill: paint a component to count it, and counting components by launching from every unvisited cell (Bosses 1, 2)
• DFS with return values: the recursion hands answers up, areas, verdicts, sums (Boss 2)
• Cloning with a visited map: old node to new node, create on first sight, look up ever after (Boss 3)
• Multi-source BFS: drop every source in the queue at once, one wave, all distances (Boss 4)
• BFS levels as time: each ring of the expansion is one minute, one step, one generation (Boss 5)
• Reverse traversal from the targets: when "can reach X" is the question, start at X and swim upstream (Boss 6)
• Border-first survival: mark what's safe from the edges inward, condemn the rest (Boss 7)
• Three-state cycle detection: unvisited, in-progress, done, a gray node seen twice is a directed cycle (Boss 8)
• Kahn's topological sort: peel zero in-degree nodes, a valid order falls out or a cycle blocks it (Boss 9)
• Tree = exactly n minus 1 edges and connected: two cheap checks, no cycle hunt needed (Boss 10)
• Union-find: parent pointers, path compression, union by size, groups in near-constant time (Boss 11)
• Live cycle catching: process edges in order, the first failed union closed the loop (Boss 12)
• Implicit graphs + BFS: no edge list, just states and a move rule, shortest path anyway (Boss 13)

Next dungeon: 1-D Dynamic Programming. Climbing stairs, robbing houses, and the quiet realization that most brute-force recursion recomputes the same sub-answers thousands of times. The fix is almost insulting: write the answer down the first time. Recursion grows a memory, and problems that looked exponential collapse into a single walk down an array.

See you in Dungeon 12.