Word Ladder (LeetCode 127)

The problem

You get a begin word, an end word and a list of allowed words wordList. A transformation changes exactly one letter at a time, and every intermediate word must be in wordList (begin itself does not have to be). Return the number of words in the shortest sequence from begin to end, counting both ends, or 0 if no sequence exists.

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

hit -> hot -> dot -> dog -> cog uses 5 words, and there is no shorter chain.

How to think about it

Start with brute force. Try every possible sequence with backtracking: from the current word, recurse into every unused word that differs by one letter, and keep the shortest chain that reaches end. The number of paths explodes exponentially.

The key insight: this is a shortest path in a graph. Make each word a node, and join two words with an edge if they differ in exactly one position. “Fewest transformations” is “fewest edges”. Every edge costs the same, so the right tool is BFS: the first time BFS reaches end, it got there by the shortest route.

Don’t build the graph up front. Comparing every pair of words is O(N² · L). Instead, generate neighbours on the fly: for each position in the current word, try all 26 letters and keep the results that are in the word set. That is L · 26 candidates per word, each checked in O(1) average with a set (plus O(L) to build the string).

Remove a word from the set when you queue it. That marks it visited, so it can’t be queued again by a longer path. It also shrinks the set as the search goes on.

Which pattern is this? BFS on an implicit graph. The tell is “minimum number of steps”, where each step is a small change to a state.

Approach

1. Put wordList in a set words. If end isn’t in it, return 0.
2. Start a queue with (begin, 1).
3. Pop (word, d). If word == end, return d.
4. For each position i and each letter ch, form nxt. If nxt is in words, remove it and push (nxt, d + 1).
5. If the queue empties, return 0.

Solution

from collections import deque

def ladder_length(begin, end, wordList):
    words = set(wordList)                         # O(1) membership; doubles as "unvisited"
    if end not in words: return 0
    q = deque([(begin, 1)])                       # (word, words in the chain so far)
    while q:
        word, d = q.popleft()
        if word == end: return d                  # BFS: first arrival is the shortest
        for i in range(len(word)):
            for ch in "abcdefghijklmnopqrstuvwxyz":
                nxt = word[:i] + ch + word[i+1:]  # every one-letter edit
                if nxt in words:
                    words.remove(nxt); q.append((nxt, d + 1))   # mark visited when queued
    return 0
# ladder_length("hit","cog",["hot","dot","dog","lot","log","cog"]) -> 5

Dry run

On the example:

Complexity

• Time: O(N · L² · 26) strictly, often quoted as O(N · L · 26). Each of the N words is popped at most once and tries L · 26 candidates. Building each candidate string is O(L), which gives the extra factor of L; with short words it’s treated as a constant.
• Space: O(N · L) for the word set and the queue (O(N) words of length L).

Edge cases and pitfalls

• end not in wordList: return 0 straight away.
• No path: ladder_length("hit", "cog", ["hot","dot","dog","lot","log"]) returns 0 because cog is missing; if cog is present but unreachable, the queue empties and it also returns 0.
• Counting edges instead of words. The answer counts words, so begin starts at 1.
• Marking visited on pop instead of on push can queue the same word many times and blow up the run time.
• DFS finds a path, not the shortest one. For a big speed-up, run BFS from both ends at once (bidirectional BFS).

Related problems

• Rotting Oranges (LeetCode 994): BFS distances, level by level, on a grid.
• Minimum Depth of Binary Tree (LeetCode 111): BFS that returns at the first target it reaches.
• Network Delay Time (LeetCode 743): shortest paths when edges have weights, where BFS gives way to Dijkstra.