Skip to main content

25. Word Ladder

hardAsked at Asana

Find the shortest transformation sequence from one word to another by changing one letter at a time — Asana uses BFS shortest-path reasoning when computing the minimum number of workflow-state transitions needed to move a task from one status to another under a rule graph.

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

Problem

Given two words beginWord and endWord, and a dictionary wordList, return the number of words in the shortest transformation sequence from beginWord to endWord. Each transformed word must exist in the wordList and differ by exactly one letter. 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
  • beginWord, endWord, and wordList[i] 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 (5 words).

Example 2

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

Explanation: endWord 'cog' is not in wordList — impossible.

Approaches

1. BFS with neighbor generation

BFS from beginWord. At each step, try replacing every character with a-z and check if the result is in the word set. Track level to count the path length.

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;

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

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

  return 0;
}

Tradeoff:

2. Bidirectional BFS (optimal)

Run BFS simultaneously from both beginWord and endWord, alternating the smaller frontier each step. Stops when the frontiers intersect — dramatically reduces search space.

Time
O(M^2 * N)
Space
O(M^2 * N) with smaller constant
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]);
  const visited = new Set([beginWord, endWord]);
  let level = 1;

  while (front.size > 0 && back.size > 0) {
    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 level + 1;
          if (wordSet.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.add(candidate);
          }
        }
      }
    }
    front = next;
    level++;
  }

  return 0;
}

Tradeoff:

Asana-specific tips

Word Ladder is an Asana hard-round signal problem. Start by framing it as 'shortest path in an unweighted graph — BFS gives the guarantee.' Name the time complexity as O(M^2 * N) where M = word length, N = wordList size and explain why (M characters * 26 replacements * N words). Bidirectional BFS is the optimization to mention if asked for improvement — it shrinks the explored frontier from O(b^d) to O(b^(d/2)). Interviewers reward the candidate who thinks like a system designer: 'In production with millions of words I'd precompute a pattern-to-words index like *it → [hit, bit, sit] to avoid the inner loop.'

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

Practice these live with InterviewChamp.AI →