Skip to main content

127. Word Ladder

mediumAsked at Duolingo

Find the shortest transformation sequence from one word to another by changing one letter at a time — the BFS word-graph search that mirrors how Duolingo's word-learning path finds the fewest morphological steps between a learner's current vocabulary and a target word.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given a beginWord, an endWord, and a wordList dictionary, return the number of words in the shortest transformation sequence from beginWord to endWord, where each step changes exactly one letter and every intermediate word must exist in the dictionary. Return 0 if no such sequence exists.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • All words have the same length and consist of lowercase English letters
  • beginWord != endWord

Examples

Example 1

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

Explanation: hit → hot → dot → dog → cog (5 words).

Example 2

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

Explanation: endWord 'cog' is not in wordList.

Approaches

1. BFS — try all one-letter replacements

BFS from beginWord; at each step, generate all strings one character away and enqueue those that are in the dictionary and not yet visited.

Time
O(M^2 * N) where M = word length, N = wordList size
Space
O(M^2 * N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  const queue = [[beginWord, 1]];
  const visited = new Set([beginWord]);

  while (queue.length) {
    const [word, steps] = queue.shift();
    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 (next === endWord) return steps + 1;
        if (wordSet.has(next) && !visited.has(next)) {
          visited.add(next);
          queue.push([next, steps + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff:

2. Bidirectional BFS

Expand from both beginWord and endWord simultaneously; switch to the smaller frontier each step — reduces effective branching factor dramatically.

Time
O(M^2 * N)
Space
O(M^2 * N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;

  let frontA = new Set([beginWord]);
  let frontB = new Set([endWord]);
  let steps = 1;

  while (frontA.size && frontB.size) {
    if (frontA.size > frontB.size) [frontA, frontB] = [frontB, frontA];
    const next = new Set();
    for (const word of frontA) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const candidate = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (frontB.has(candidate)) return steps + 1;
          if (wordSet.has(candidate)) {
            next.add(candidate);
            wordSet.delete(candidate);
          }
        }
      }
    }
    frontA = next;
    steps++;
  }
  return 0;
}

Tradeoff:

Duolingo-specific tips

Duolingo's dictionary and morphological adjacency problems are a direct analogue of Word Ladder — the product literally maps how close words are to each other to build learning progressions. Interviewers want to see you build the wordSet upfront for O(1) lookup, mark visited words by deleting from the set rather than maintaining a separate visited structure, and eventually describe bidirectional BFS. Expect the question: 'How would you store the actual path, not just the length?' — answer: track parent pointers in a Map.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →