127. Word Ladder
hardAsked at AmazonFind the length of the shortest transformation from beginWord to endWord, changing one letter at a time. Amazon asks this to test whether you reach for BFS on an implicit graph and articulate the shortest-path-on-unweighted-edges insight.
By Sam K., Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in Amazon loops.
- Glassdoor (2026-Q1)— Amazon SDE II onsite reports cite this as the graph round.
- Blind (2025-09)— Recurring Amazon interview problem.
Problem
A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence of words. Every adjacent pair of words differs by a single letter. Every si for 1 <= i <= k is in wordList. Given two words, beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, or 0 if no such sequence exists.
Constraints
1 <= beginWord.length <= 10endWord.length == beginWord.length1 <= wordList.length <= 5000wordList[i].length == beginWord.lengthbeginWord, endWord, and wordList[i] consist of lowercase English letters.beginWord != endWordAll the words in wordList are unique.
Examples
Example 1
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]5Example 2
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]0Approaches
1. Single-source BFS with neighbor enumeration
Standard BFS. At each word, try replacing each position with a-z; check membership in wordList.
- Time
- O(N * L * 26)
- Space
- O(N * L)
function ladderLength(beginWord, endWord, wordList) {
const set = new Set(wordList);
if (!set.has(endWord)) return 0;
const q = [[beginWord, 1]];
const seen = new Set([beginWord]);
while (q.length) {
const [word, dist] = q.shift();
if (word === endWord) return dist;
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) {
const next = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (set.has(next) && !seen.has(next)) {
seen.add(next);
q.push([next, dist + 1]);
}
}
}
}
return 0;
}Tradeoff: Standard BFS. Neighbor enumeration is O(L * 26) per node.
2. Bidirectional BFS (optimal)
BFS from both ends; expand the smaller frontier. Meet in the middle.
- Time
- O(N * L * 26)
- Space
- O(N * L)
function ladderLengthBi(beginWord, endWord, wordList) {
const set = new Set(wordList);
if (!set.has(endWord)) return 0;
let beginSet = new Set([beginWord]);
let endSet = new Set([endWord]);
const visited = new Set();
let dist = 1;
while (beginSet.size && endSet.size) {
if (beginSet.size > endSet.size) [beginSet, endSet] = [endSet, beginSet];
const next = new Set();
for (const word of beginSet) {
for (let i = 0; i < word.length; i++) {
for (let c = 97; c <= 122; c++) {
const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
if (endSet.has(cand)) return dist + 1;
if (set.has(cand) && !visited.has(cand)) {
visited.add(cand);
next.add(cand);
}
}
}
}
beginSet = next;
dist++;
}
return 0;
}Tradeoff: Halves the effective depth — typically 100x-1000x faster on dense word lists. Mention this after the standard BFS.
Amazon-specific tips
Amazon interviewers want BFS articulation. State out loud: 'BFS guarantees shortest path on unweighted graphs. The first time we reach endWord, we've found the minimum.' Bidirectional BFS is the senior-IC signal — mention it as the optimization.
Common mistakes
- Building an explicit adjacency list (wasteful — enumerate neighbors on the fly).
- Using DFS — doesn't give shortest path without extra bookkeeping.
- Forgetting that endWord must be in wordList (return 0 if not).
Follow-up questions
An interviewer at Amazon may pivot to one of these next:
- Word Ladder II (LC 126) — return all shortest paths.
- What if some edges had costs (Dijkstra)?
- What if the alphabet were huge?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why BFS not DFS?
BFS explores by distance. First arrival at endWord IS the shortest. DFS could find a longer path first.
Is bidirectional BFS expected?
Often yes. State it after the standard solution. If you have time, implement it. If not, articulating it earns nearly the same signal.