📚 Table of Contents
📋 Problem Statement
You can change exactly one character per step, and every intermediate word must exist in
wordList. Return number of words in shortest sequence, or 0 if no
path exists.
Example
beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]Output: 5 via hit -> hot -> dot -> dog -> cog
🎯 Real-World Analogy
Airport Connections with One-Letter Gate Changes
Each word is an airport code. You can only fly to another code if it differs by one letter. BFS finds the minimum number of flights to destination.
💡 Key Insights
- This is an unweighted shortest-path problem -> BFS is optimal.
- Naively comparing every pair is expensive.
- Wildcard patterns (e.g.
h*t) create adjacency buckets efficiently. - Mark words visited when queued to avoid duplicate work.
💻 Solution Approaches
Approach 1: Pairwise Graph + BFS
Time: O(W² * L) | Space: O(W²)
Approach 2: Pattern Map + BFS (Recommended)
Time: O(W * L²) typical | Space: O(W * L)
Python Implementation
from collections import defaultdict, deque
from typing import List
def ladder_length(begin_word: str, end_word: str, word_list: List[str]) -> int:
if end_word not in word_list:
return 0
L = len(begin_word)
patterns = defaultdict(list)
all_words = word_list + [begin_word]
for word in all_words:
for i in range(L):
patterns[word[:i] + '*' + word[i + 1:]].append(word)
queue = deque([(begin_word, 1)])
visited = {begin_word}
while queue:
word, distance = queue.popleft()
if word == end_word:
return distance
for i in range(L):
pattern = word[:i] + '*' + word[i + 1:]
for neighbor in patterns[pattern]:
if neighbor not in visited:
visited.add(neighbor)
queue.append((neighbor, distance + 1))
patterns[pattern] = []
return 0
JavaScript Implementation
function ladderLength(beginWord, endWord, wordList) {
if (!wordList.includes(endWord)) return 0;
const L = beginWord.length;
const patterns = new Map();
const allWords = [...wordList, beginWord];
for (const word of allWords) {
for (let i = 0; i < L; i += 1) {
const pattern = `${word.slice(0, i)}*${word.slice(i + 1)}`;
if (!patterns.has(pattern)) patterns.set(pattern, []);
patterns.get(pattern).push(word);
}
}
const queue = [[beginWord, 1]];
const visited = new Set([beginWord]);
while (queue.length) {
const [word, distance] = queue.shift();
if (word === endWord) return distance;
for (let i = 0; i < L; i += 1) {
const pattern = `${word.slice(0, i)}*${word.slice(i + 1)}`;
const neighbors = patterns.get(pattern) || [];
for (const neighbor of neighbors) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push([neighbor, distance + 1]);
}
}
patterns.set(pattern, []);
}
}
return 0;
}
🔍 Step-by-Step Walkthrough
For hit -> cog:
Level 1: hit
Level 2: hot
Level 3: dot, lot
Level 4: dog, log
Level 5: cog reached
⚡ Complexity Analysis
Time: Building patterns costs O(W * L²) due to slicing. BFS traversal is bounded by processed pattern edges.
Space: O(W * L) for pattern map plus visited/queue state.
🔧 Edge Cases
endWordmissing from dictionary -> return 0 immediately.beginWord == endWord(if allowed by variant).- Disconnected components in transformation graph.
- Large dictionaries with many near-collisions.
🧪 Test Cases
Python
def test_ladder_length():
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) == 5
assert ladder_length("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) == 0
assert ladder_length("a", "c", ["a", "b", "c"]) == 2
print("all tests passed")JavaScript
function testLadderLength() {
console.assert(
ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log", "cog"]) === 5,
"test 1"
);
console.assert(
ladderLength("hit", "cog", ["hot", "dot", "dog", "lot", "log"]) === 0,
"test 2"
);
console.assert(ladderLength("a", "c", ["a", "b", "c"]) === 2, "test 3");
console.log("all tests passed");
}💼 Interview Tips
- Call out shortest path -> BFS before implementation details.
- Explain wildcard pattern indexing to avoid O(W²) adjacency scans.
- Mention bidirectional BFS as a possible optimization.
- Be careful with visited timing to prevent queue blowup.
🎓 Key Takeaways
- Word Ladder is BFS over an implicit graph.
- Pattern mapping is the key performance unlock.
- Correct visited handling controls both correctness and speed.