31. Word Ladder

hardAsked at Spotify

Find the shortest transformation sequence from one word to another changing one letter at a time — BFS on an implicit graph that mirrors Spotify's genre-to-genre shortest-path queries in its music taxonomy graph.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-26

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 such that each adjacent pair differs by exactly one letter and each word in the sequence is in wordList. If no such sequence exists, return 0.

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

Explanation: hit → hot → dot → dog → cog

Example 2

Input

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

Output

Explanation: cog is not in wordList.

Approaches

1. BFS with word mutation

BFS level by level; at each word try replacing every character with a-z. If the result is in the word set and unvisited, enqueue it. Shortest path = BFS level when endWord is reached.

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 (optimal)

Simultaneously BFS from both beginWord and endWord; alternate which frontier to expand by picking the smaller one. Meets in the middle, reducing the search space from O(b^d) to O(b^(d/2)).

Time: O(M^2 * N) with smaller constant
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]);
  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 w = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (back.has(w)) return steps + 1;
          if (wordSet.has(w)) { next.add(w); wordSet.delete(w); }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff:

Spotify-specific tips

Spotify graph engineers care about bidirectional BFS because music taxonomy traversal can have branching factors in the hundreds — reducing exponent from d to d/2 is significant at scale. Mentioning 'meet in the middle' by name, then explaining why it works, consistently impresses Spotify interviewers in the data-infrastructure 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 Spotify interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →