21. Word Ladder

hardAsked at Tesla

Find the shortest transformation sequence between two words — Tesla maps this BFS shortest-path structure to vehicle-mode state graphs, where each valid one-step transition (Park to Reverse to Neutral to Drive) must be reachable without unsafe jumps.

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

Problem

Given a beginWord, an endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord such that only one letter changes at each step and every intermediate word is in the wordList. Return 0 if no sequence exists.

Constraints

1 <= beginWord.length <= 10
endWord.length == beginWord.length
1 <= wordList.length <= 5000
beginWord, endWord, and all words in wordList consist of lowercase English letters only

Examples

Example 1

Input

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

Output

Explanation: Shortest path: hit -> hot -> dot -> dog -> cog (5 words).

Example 2

Input

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

Output

Explanation: endWord not in wordList; no transformation exists.

Approaches

1. BFS with word set

Level-by-level BFS from beginWord; for each word generate all one-letter variants and check the word set. First time endWord is reached, return level count.

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 BFS from both beginWord and endWord simultaneously; halt when the two frontiers meet. Cuts search space from O(b^d) to O(b^(d/2)).

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 front = new Set([beginWord]);
  let back = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let steps = 1;
  while (front.size && back.size) {
    // Always expand the smaller frontier
    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) && !visited.has(candidate)) {
            visited.add(candidate);
            next.add(candidate);
          }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff:

Tesla-specific tips

Tesla surfaces this in system-design-adjacent coding rounds to assess whether you think about search space size. The vehicle-mode transition analogy is real — the state graph for PRND modes plus charge states is exactly this structure. Arrive at bidirectional BFS on your own; candidates who stick to single-direction BFS pass but don't stand out. Always check that endWord is in wordList before touching the queue.

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

Practice these live with InterviewChamp.AI →