LeetCode 127: Word Ladder — Python Solution

LeetCode 127: Word Ladder is a Hard graph bfs problem. This Python walkthrough develops a wildcard-neighbor BFS solution, ties every code decision to a concrete invariant, and includes the regression check used before publication.

This independent guide paraphrases the task rather than reproducing LeetCode’s prompt. Use the official page for the exact statement, examples, constraints, and submission runner.

Recognizing the pattern

BFS explores an unweighted state graph in increasing move count, so the first arrival gives a shortest transformation.

For this problem specifically, index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern. The invariant worth writing beside the code is: The first BFS layer reaching a word uses the shortest transformation sequence.

Step-by-step algorithm

1. Identify the input state consumed by ladderLength(beginWord, endWord, wordList) and initialize the data required by the wildcard-neighbor BFS pattern.
2. Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.
3. After each update, verify the page’s central invariant: The first BFS layer reaching a word uses the shortest transformation sequence.
4. Finish only after the boundary behavior is covered: The end word must be in the dictionary; each transformation changes exactly one character.

Python solution

from collections import defaultdict, deque

class Solution:
    def ladderLength(self, beginWord, endWord, wordList):
        if endWord not in wordList: return 0
        patterns = defaultdict(list)
        width = len(beginWord)
        for word in wordList:
            for i in range(width): patterns[word[:i] + "*" + word[i + 1:]].append(word)
        queue, seen = deque([(beginWord, 1)]), {beginWord}
        while queue:
            word, distance = queue.popleft()
            for i in range(width):
                pattern = word[:i] + "*" + word[i + 1:]
                for neighbor in patterns[pattern]:
                    if neighbor == endWord: return distance + 1
                    if neighbor not in seen:
                        seen.add(neighbor); queue.append((neighbor, distance + 1))
                patterns[pattern] = []
        return 0

Reading the implementation

The main entry point is ladderLength(beginWord, endWord, wordList). The named working state includes patterns, width, queue, word, pattern; those variables make the wildcard-neighbor BFS state visible instead of hiding it in incidental control flow.

The implementation uses 5 loops with separate responsibilities, so preprocessing and the main traversal can each stay linear in their own input. In concrete terms, index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern.

Correctness argument

Initialization. The starting state is the only item in the first frontier, so its distance or level is exact.

Preservation. Index words by wildcard patterns, then BFS from the beginning word through words sharing a pattern. Because the queue processes earlier layers first, the first BFS layer reaching a word uses the shortest transformation sequence.

Termination. Each state is accepted at most once. The first accepted goal therefore has the minimum possible layer, or exhausting the queue proves no valid path exists.

Complexity and trade-offs

O(NL^2) preprocessing and traversal time and O(NL) space. The auxiliary-space figure excludes the returned output unless the output itself is the structure being built.

DFS can determine reachability but cannot stop at the first found path when a minimum number of moves is required. That comparison is useful in an interview because it explains why the final implementation is preferable, not merely that it passes.

Regression check

The published implementation belongs to a 100-problem suite that is compiled and exercised behaviorally before deployment.

One reference assertion from that suite is shown below. It targets the normal path while the edge conditions in the next section cover the failure-prone boundaries.

assert Solution().ladderLength("hit","cog",["hot","dot","dog","lot","log","cog"])==5

Common mistakes and edge cases

• Problem-specific boundary: The end word must be in the dictionary; each transformation changes exactly one character.
• Pattern-level pitfall: Generate only legal neighbors, mark them before enqueueing, and count layers consistently with the problem’s definition of a move.
• Invariant check: after every update, confirm that the first BFS layer reaching a word uses the shortest transformation sequence.

Interview review checklist

• Explain why wildcard-neighbor BFS matches the structure of this input.
• State the invariant in one sentence before tracing code: The first BFS layer reaching a word uses the shortest transformation sequence.
• Derive O(NL^2) preprocessing and traversal time and O(NL) space from how many times each element or state is visited.
• Test the boundary explicitly: The end word must be in the dictionary; each transformation changes exactly one character.

Browse the searchable 100 LeetCode Python Solutions hub. Previous: 433. Minimum Genetic Mutation · Next: 208. Implement Trie (Prefix Tree)