Skip to main content

25. Word Ladder

hardAsked at Quora

Find the shortest transformation sequence between two words — Quora uses this BFS-on-word-graph pattern to power their 'related topics' traversal, finding the minimum conceptual hops between two knowledge domains.

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

Problem

Given a beginWord, an endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord where each intermediate word must differ by exactly one letter and exist in the wordList. Return 0 if no such sequence exists.

Constraints

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • All words consist of lowercase English letters
  • beginWord != endWord
  • All words in wordList are unique

Examples

Example 1

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

Explanation: hit → hot → dot → dog → cog is length 5.

Example 2

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

Explanation: endWord 'cog' is not reachable.

Approaches

1. BFS with one-letter neighbours

Build the graph implicitly during BFS: for each word in the queue, try replacing each position with a–z; if the result is in the word set, enqueue it. BFS guarantees shortest path.

Time
O(M^2 * N) where M = word length, N = wordList size
Space
O(M * 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

Run BFS simultaneously from beginWord and endWord; alternate expanding the smaller frontier. Reduces the effective branching factor from b^d to 2*b^(d/2).

Time
O(M^2 * N) — roughly half the work of one-directional BFS
Space
O(M * N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  let front = new Set([beginWord]);
  let back = new Set([endWord]);
  let steps = 1;
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set();
    for (const word of front) {
      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 (back.has(candidate)) return steps + 1;
          if (wordSet.has(candidate)) {
            next.add(candidate);
            wordSet.delete(candidate);
          }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff:

Quora-specific tips

Quora's interviewers use this problem to separate senior from mid-level: mention bidirectional BFS unprompted and walk through why halving the frontier depth gives a squared reduction in nodes visited. That's the exact reasoning their search infrastructure team applies to large-scale graph traversals.

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 Quora interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →