Graphs · LC #127
Word Ladder
Find the shortest word transformation sequence using BFS on an implicit graph where edges connect words differing by exactly one character.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
A transformation sequence from word `beginWord` to `endWord` using a dictionary `wordList` is a sequence `beginWord → s1 → s2 → ... → sk` such that: - Every adjacent pair differs in exactly one letter. - Every `si` for `1 <= i <= k` is in `wordList`. - `sk == endWord`. Return the **number of words** in the shortest transformation sequence, or 0 if no such sequence exists.
Sample I/O
Input: beginWord="hit", endWord="cog",
wordList=["hot","dot","dog","lot","log","cog"]
Output: 5 (hit→hot→dot→dog→cog)
Input: beginWord="hit", endWord="cog",
wordList=["hot","dot","dog","lot","log"]
Output: 0 (cog not in wordList)Time: O(M²×N) · Space: O(M×N)
Intuition
How to Think About It
Intuition
Model words as graph nodes; edges connect words differing by exactly one character. The shortest path from beginWord to endWord in this implicit graph is found by BFS (BFS explores level by level, guaranteeing minimum steps). We never need to explicitly build the graph - generate neighbors on the fly by substituting each character position with a-z.
Core Concept
BFS on implicit word graph. For each word at the current BFS level, generate all single-character mutations. If a mutation is in wordSet and not yet visited, enqueue it and remove from set (visited marking). If mutation equals endWord, return current level + 1. Time: O(M² × N) where M = word length, N = wordList size.
When to use
Finding shortest path in an unweighted graph (implicit or explicit). When the graph is too large to enumerate edges explicitly. When the state space can be explored level by level.
When NOT to use
When shortest path in a weighted graph is needed (Dijkstra). When all shortest paths are needed (more complex BFS variant). When the transformation rule is more complex than single-char change.
Key Insights
What to Know Cold
- Remove words from wordSet when enqueued, not when dequeued - prevents enqueuing the same word multiple times.
- Checking endWord early (before enqueueing) saves one BFS level.
- Bidirectional BFS cuts complexity from O(b^d) to O(b^(d/2)) where b=branching factor, d=depth.
- The implicit graph has no pre-built edge list - neighbors generated on-the-fly by character substitution.
- Storing beginWord as the only level-0 node means the answer is steps + 1 (counting beginWord in the sequence).
1 example
Worked Examples
BFS shortest word transformation
hit→cog via hot→dot→dog path of length 5.
BFS level-by-level; try all 26-char substitutions at each position; dequeue and count levels.
function ladderLength(begin: string, end: string, wordList: string[]): number {
const wordSet = new Set(wordList);
if (!wordSet.has(end)) return 0;
const q: string[] = [begin];
let steps = 1;
while (q.length) {
const size = q.length;
for (let i = 0; i < size; i++) {
const word = q.shift()!;
for (let j = 0; j < word.length; j++) {
for (let c = 97; c <= 122; c++) {
const next = word.slice(0, j) + String.fromCharCode(c) + word.slice(j + 1);
if (next === end) return steps + 1;
if (wordSet.has(next)) { q.push(next); wordSet.delete(next); }
}
}
}
steps++;
}
return 0;
}Output: 5
Tests BFS fluency on an implicit graph. Google and Meta use this to probe whether candidates can model non-obvious problems as graph traversals and implement BFS with correct level-tracking.