LeetCode · #127

Word Ladder Solution

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time, where each intermediate word must be in a given wordList.

Section One · Problem

Problem Statement

🏷️

Difficulty

Hard

🔗

LeetCode

Problem #127

🏗️

Pattern

Graph — BFS shortest path on word graph

Given beginWord, endWord, and a wordList, find the number of words in the shortest transformation sequence from begin to end, where each step changes exactly one letter and every intermediate word must be in wordList. Return 0 if no sequence exists.

Example

 Input: beginWord = "hit", endWord = "cog"
wordList  = ["hot","dot","dog","lot","log","cog"]
Output: 5 // "hit" → "hot" → "dot" → "dog" → "cog"  (5 words) 

Constraints

 • 1 ≤ beginWord.length ≤ 10  (all words same length m) • 1 ≤ wordList.length ≤ 5000  ← BFS with word set required • All words consist of lowercase English letters • endWord may or may not be in wordList 

Section Two · Approach 1

BFS with Direct Neighbor Generation — O(m²·n)

BFS from beginWord. At each step, for the current word, generate all possible one-letter variations by replacing each character with a-z and check if the result is in the word set. If yes and unvisited, enqueue it. Return the level count when endWord is reached.

Why BFS is required

BFS processes nodes level by level, where each level represents one more transformation. The first time endWord is dequeued, the level number is the shortest path length. DFS cannot guarantee shortest path unless it exhaustively explores all paths.

Can we build the graph faster?

Bottleneck: For each word (n words), we try m positions × 26 letters = 26m variations, checking each in the word set O(m) for hashing. Total: O(n · 26m · m) = O(m²·n). The wildcard pattern approach pre-groups words so that neighbors are looked up via a precomputed map instead of re-hashing on every BFS step — same asymptotic but much faster in practice for large word lists.

Java — BFS + direct letter substitution

 import java.util.*;
class Solution {
public int ladderLength(String begin, String end, List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(end)) return 0;
Queue<String> q = new LinkedList<>();
        q.offer(begin);
        wordSet.remove(begin); // treat visited as removed int level = 1;
while (!q.isEmpty()) {
int size = q.size();
while (size-- > 0) {
char[] word = q.poll().toCharArray();
for (int i = 0; i < word.length; i++) {
char orig = word[i];
for (char c = 'a'; c <= 'z'; c++) {
                        word[i] = c;
String next = new String(word);
if (next.equals(end)) return level + 1;
if (wordSet.contains(next)) {
                            wordSet.remove(next); // remove = mark visited
q.offer(next);
                        }
                    }
                    word[i] = orig;
                }
            }
            level++;
        }
return 0;
    }
}

Python — BFS + direct letter substitution

 from collections import deque
class Solution:
def ladderLength(self, begin: str, end: str, wordList: list[str]) -> int:
        words = set(wordList)
if end not in words: return 0
q = deque([(begin, 1)])
        words.discard(begin)
while q:
            word, level = q.popleft()
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
                    nw = word[:i] + c + word[i+1:]
if nw == end: return level + 1 if nw in words:
                        words.discard(nw)
                        q.append((nw, level + 1))
return 0 

Metric	Value
Time	O(m² · n) — n words × m positions × 26 letters × O(m) hash
Space	O(m · n) — word set + queue

Section Three · Approach 2

BFS with Wildcard Pattern Map — O(m²·n)

Pre-process all words into a pattern map: for each word and each position, generate a wildcard like "h*t" for "hot" at position 1. Store pattern → [matching words]. During BFS, replace each character position with * to get patterns and look up all neighbor words instantly.

💡 Mental model: Imagine a telephone directory organized by "what the word sounds like with one syllable blurred." You create index entries like "h_t" → [hat, hit, hot, hut, hbt, ...]. When you want to find all words one letter away from "hit," you look up "_it", "h_t", and "hi_" in the directory — each lookup gives you a pre-grouped list of neighbors. This is faster than scanning the entire dictionary letter by letter every time.

Algorithm — wildcard pre-processing + BFS

Build pattern map: for each word w and position i, add w to map[w with w[i]='*'].
BFS: start with (beginWord, level=1). For each word, generate all m patterns and look up neighbors. Skip already-visited words.
Return level + 1 when endWord is a neighbor, else 0.

🎯 When to recognize this pattern:

"Shortest path in a graph where edges are implied by a transformation rule" — model as BFS on an implicit graph.
The signal is: words/strings, change one character at a time, find minimum steps.
Pre-grouping by wildcard patterns is the standard interview optimization.
Used in LC 126 (Word Ladder II — reconstruct all shortest paths, harder variant).

Why remove from word set instead of a separate visited set:

Since we process each word at most once (the first time it's dequeued gives the shortest path), removing from the word set when enqueueing serves as the visited marker.
A separate HashSet<String> visited would also work but uses extra space and has the same membership-check cost.

Section Four · Trace

Visual Walkthrough

Trace BFS from "hit" to "cog" with word list [hot, dot, dog, lot, log, cog].

Word Ladder — BFS Level by Level

Section Five · Implementation

Code — Java & Python

Java — BFS with letter substitution (clean variant)

 import java.util.*;
class Solution {
public int ladderLength(String begin, String end,
List<String> wordList) {
Set<String> wordSet = new HashSet<>(wordList);
if (!wordSet.contains(end)) return 0;
Queue<String> q = new LinkedList<>();
        q.offer(begin);
        wordSet.remove(begin); // remove start = mark visited int level = 1;
while (!q.isEmpty()) {
int sz = q.size();
while (sz-- > 0) {
char[] chars = q.poll().toCharArray();
for (int i = 0; i < chars.length; i++) {
char orig = chars[i];
for (char c = 'a'; c <= 'z'; c++) {
if (c == orig) continue;
                        chars[i] = c;
String next = new String(chars);
if (next.equals(end)) return level + 1;
if (wordSet.remove(next)) // remove = enqueue + mark visited
q.offer(next);
                    }
                    chars[i] = orig; // restore for next position
}
            }
            level++;
        }
return 0;
    }
}

Python — BFS with wildcard pattern map

 from collections import defaultdict, deque
class Solution:
def ladderLength(self, begin: str, end: str, wordList: list[str]) -> int:
if end not in set(wordList): return 0
m = len(begin)
# Pre-build wildcard → word list map
patterns: dict = defaultdict(list)
for word in [begin] + wordList:
for i in range(m):
                patterns[word[:i] + '*' + word[i+1:]].append(word)

        visited = {begin}
        q = deque([(begin, 1)])
while q:
            word, level = q.popleft()
for i in range(m):
                pat = word[:i] + '*' + word[i+1:]
for nb in patterns[pat]:
if nb == end: return level + 1 if nb not in visited:
                        visited.add(nb)
                        q.append((nb, level + 1))
return 0 

Section Six · Analysis

Complexity Analysis

Approach	Time	Space	Trade-off
DFS / exhaustive search	O(n!)	O(n)	Cannot guarantee shortest path; exponential
BFS direct substitution	O(m² · n)	O(m · n)	Simple; generates same variations during BFS
BFS + wildcard map ← optimal	O(m² · n)	O(m · n)	Precomputed patterns avoid recomputing variations; faster in practice

Why BFS guarantees the shortest path:

BFS explores words in order of increasing transformation distance from beginWord.
Level 1 = words one transformation away; level 2 = two transformations, etc.
The first time endWord appears in the BFS frontier, that level is definitively the minimum.
Any path found later would be longer.

Section Seven · Edge Cases

Edge Cases & Pitfalls

Case	Input	Why It Matters
endWord not in wordList	`endWord="cog"` missing	No path possible. Return 0 immediately — saves BFS.
begin == end	Same word	Constraints say they differ (beginWord ≠ endWord), but if same, distance = 1 (just one word).
endWord directly reachable	One letter change from begin	BFS finds it in level 2. Returns 2.
No path exists	Disconnected word graph	BFS exhausts queue without finding endWord. Return 0.
Not removing from word set on enqueue	any	The same word gets enqueued multiple times via different predecessors. BFS still terminates but is slower and may produce wrong level count.
Large word list (5000 words)	max n	O(m²·n) = O(100 · 5000) = 500,000 operations — fine.

⚠ Common Mistake: Marking a word as visited (removing from set) when dequeued instead of when enqueued. If you wait until dequeue to mark visited, the same word can be enqueued multiple times before any of those enqueue events is processed — exponentially bloating the queue. Always remove/mark when adding to the queue, not when removing from it. This is the standard "mark on enqueue" BFS rule.

← Back to Graph problems

LearningTree

LC 127 · Word Ladder — Solution & Explanation | DSA Guide