Skip to main content

31. Word Ladder

hardAsked at Tripadvisor

Find the shortest transformation sequence between two words — Tripadvisor's destination-graph team applies BFS shortest-path reasoning to compute minimum-hop routes between destination nodes in their travel-graph recommendation engine.

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

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord → s1 → s2 → ... → sk such that every adjacent pair differs by exactly one letter, every si is in wordList, and sk == endWord. Given beginWord, endWord, and wordList, return the number of words in the shortest such transformation sequence, 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 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, no transformation sequence exists.

Approaches

1. BFS level-by-level

BFS from beginWord. For each word in the queue, generate all single-character mutations; if a mutation is in the word set and unvisited, enqueue it. Return level count when endWord is reached.

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) {
    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 two simultaneous BFS frontiers from beginWord and endWord. At each step, expand the smaller frontier. When the frontiers intersect, the path length is found. Reduces search space from O(b^d) to O(b^(d/2)).

Time
O(M^2 * N) worst-case, O(b^(d/2)) in practice
Space
O(M^2 * 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]);
  const visited = new Set([beginWord, endWord]);
  let level = 1;
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    level++;
    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;
          if (wordSet.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.add(candidate);
          }
        }
      }
    }
    front = next;
  }
  return 0;
}

Tradeoff:

Tripadvisor-specific tips

Tripadvisor's travel-graph team uses shortest-path reasoning constantly — minimum connection hops between destinations, minimal itinerary changes, shortest recommendation chains. This problem is a hard-bar question that tests whether you can translate a real graph problem (hop distance) into an implicit graph BFS. The bidirectional BFS is the differentiating answer: argue that it shrinks the search tree from the full BFS cone to two half-cones meeting in the middle, which dramatically reduces nodes visited on dense word graphs. Draw the frontier sizes to make this concrete.

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

Practice these live with InterviewChamp.AI →