Word Ladder
Asked at Amazon, Apple
Problem
Given two words (beginWord and endWord) and a word list, find the shortest transformation sequence from beginWord to endWord, changing one letter at a time. Each intermediate word must be in the word list. This is a classic BFS shortest-path problem on an implicit word graph.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | Hard | View all Amazon questions → |
| Apple | Hard | View all Apple questions → |
How to Think About It
Think of each word as a node. Two words are connected if they differ by exactly one letter. The shortest transformation is the shortest path in this unweighted graph. BFS finds shortest paths in unweighted graphs.
Brute force: for each word in the list, check if it differs by one letter from the current word. That's O(n * L) per level where n = word list size and L = word length. Total: O(n * L * n) = O(n^2 * L). Too slow.
Optimization: preprocess words into wildcard patterns. For "hot", the patterns are "ot", "ht", "ho*". All words matching the same pattern are one letter apart. This reduces neighbor lookup from O(n) to O(L * 26) = O(26L). Total: O(n * L). Much better.
Visual walkthrough for beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"]:
Patterns:
"hit" -> "it", "ht", "hi*"
"hot" -> "ot", "ht", "ho*"
"dot" -> "ot", "dt", "do*"
"dog" -> "og", "dg", "do*"
"lot" -> "ot", "lt", "lo*"
"log" -> "og", "lg", "lo*"
"cog" -> "og", "cg", "co*"
BFS from "hit":
Level 1: "hit" neighbors via patterns -> "hot" (via "ht"). Queue: ["hot"]
Level 2: "hot" neighbors -> "dot" (via "ot"), "lot" (via "lot"). Queue: ["dot","lot"]
Level 3: "dot" -> "dog" (via "do"), "lot" -> "log" (via "lo"). Queue: ["dog","log"]
Level 4: "dog" -> "cog" (via "*og"), "log" -> "cog" (via "*og"). Found! Distance = 5.
Edge cases: endWord not in wordList (return 0), no valid path (return 0), beginWord equals endWord (return 1 if endWord is in wordList, else 0).
Optimal Approach
Step 1: Put all words in a hash set for O(1) lookup.
Step 2: Preprocess words into wildcard patterns. For each word, create L patterns (one per position with "_" replacing that character). Map pattern -> list of words.
Step 3: BFS from beginWord. For each word, generate its L patterns. For each pattern, check all words matching that pattern. If a word is unvisited, add to BFS queue.
Step 4: When you reach endWord, return the number of levels + 1.
Step 5: If BFS exhausts without finding endWord, return 0.
Alternatively, without preprocessing: for each word, try all 26 letters at each position. If the resulting word is in the set, it's a neighbor. Same time complexity.
Time: O(n * L * 26) where n = word list size, L = word length. Space: O(n * L) for the pattern map.
What Trips People Up in Real Interviews
Building a full graph by comparing every word pair. That's O(n^2 * L) and too slow. Use wildcard patterns or letter-by-letter replacement to find neighbors in O(n * L).
Forgetting to mark visited words. Without a visited set, BFS loops forever on cycles (hit -> hot -> hit -> ...). Always mark words when you enqueue them, not when you dequeue.
Returning the level count instead of the transformation sequence length. The answer is the number of words in the sequence (including beginWord and endWord), not the number of edges.
Not checking if endWord exists in wordList upfront. If it doesn't, no valid transformation exists. Return 0 immediately.
Using DFS instead of BFS. DFS doesn't guarantee the shortest path. BFS explores level by level, so the first time you reach endWord, it's guaranteed to be the shortest transformation.
Solution Code
from collections import deque
def ladderLength(beginWord, endWord, wordList):
wordSet = set(wordList)
if endWord not in wordSet:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
newWord = word[:i] + ch + word[i+1:]
if newWord == endWord:
return steps + 1
if newWord in wordSet and newWord not in visited:
visited.add(newWord)
queue.append((newWord, steps + 1))
return 0Frequently Asked Questions
What is the Word Ladder problem?
Given two words (beginWord and endWord) and a word list, find the shortest transformation sequence from beginWord to endWord, changing one letter at a time. Each intermediate word must be in the word list. This is a classic BFS shortest-path problem on an implicit word graph.
How do you solve Word Ladder?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Word Ladder?
Word Ladder is asked at Amazon, Apple. It is a hard difficulty problem.
What are common mistakes on Word Ladder?
- Building a full graph by comparing every word pair. That's `O(n^2 * L)` and too slow. Use wildcard patterns or letter-by-letter replacement to find neighbors in `O(n * L)`.
- Forgetting to mark visited words. Without a visited set, BFS loops forever on cycles (hit -> hot -> hit -> ...). Always mark words when you enqueue them, not when you dequeue.
- Returning the level count instead of the transformation sequence length. The answer is the number of words in the sequence (including beginWord and endWord), not the number of edges.
- Not checking if endWord exists in wordList upfront. If it doesn't, no valid transformation exists. Return 0 immediately.
- Using `DFS` instead of `BFS`. DFS doesn't guarantee the shortest path. `BFS` explores level by level, so the first time you reach endWord, it's guaranteed to be the shortest transformation.