Skip to main content

127. Word Ladder

hardAsked at Amazon

Find 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 Alex Chen, 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 <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord, endWord, and wordList[i] consist of lowercase English letters.
  • beginWord != endWord
  • All the words in wordList are unique.

Examples

Example 1

Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
Output
5

Example 2

Input
beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
Output
0

Approaches

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.

Output

Press Run or Cmd+Enter to execute

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.

Practice these live with InterviewChamp.AI

Drill Word Ladder and other Amazon interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →