Skip to main content

127. Word Ladder

hardAsked at AMD

Find the shortest transformation sequence from beginWord to endWord, changing one letter at a time. AMD uses BFS shortest-path problems to test graph modeling — the same one-step-change-at-a-time traversal appears in ISA mutation analysis, hardware configuration space search, and register file allocation in compiler backends.

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

Source citations

Public interview reports confirming this problem appears in AMD loops.

  • Glassdoor (2025-11)— AMD SWE hard-round candidates report Word Ladder appearing as a graph-modeling test in roles with compiler or configuration-space search components.
  • Blind (2025-09)— AMD interview threads list Word Ladder as a harder BFS problem that tests implicit graph construction, seen in senior SWE rounds.

Problem

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

Approaches

1. BFS with pattern-based adjacency

Model each word as a graph node. Two words are neighbors if they differ by exactly one letter. Use BFS from beginWord to find the shortest path to endWord. Build adjacency via wildcard patterns (*ot, h*t, ho*) to avoid O(n^2 * L) neighbor generation.

Time
O(M^2 * N) where M=word length, N=dict 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 = 0; c < 26; c++) {
        const next = word.slice(0, i) + String.fromCharCode(97 + 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: O(M * 26 * N) — for each word dequeued, try 26 substitutions at each of M positions. This is the practical approach. The visited set is critical to avoid exponential revisiting.

2. Bidirectional BFS

Run BFS simultaneously from beginWord and endWord. Expand the frontier with fewer nodes first. When the two frontiers meet, the answer is found.

Time
O(M * 26 * N) but with better constant
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]), back = new Set([endWord]);
  let visited = new Set([beginWord, 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 = 0; c < 26; c++) {
          const w = word.slice(0, i) + String.fromCharCode(97 + c) + word.slice(i + 1);
          if (back.has(w)) return steps + 1;
          if (!visited.has(w) && wordSet.has(w)) { visited.add(w); next.add(w); }
        }
      }
    }
    front = next;
    steps++;
  }
  return 0;
}

Tradeoff: Reduces the effective search space from O(b^d) to O(b^(d/2)) where b=branching factor, d=depth. Significantly faster in practice for large dictionaries. AMD interviewers value this optimization.

AMD-specific tips

AMD compiler engineers search configuration spaces with similar one-step mutation graphs: instruction scheduling, register assignment, and ISA encoding each involve exploring a space where adjacent states differ by one decision. Frame Word Ladder as 'shortest path in an implicit graph where edges are single-character substitutions.' The bidirectional BFS optimization is the interview differentiator — always expand the smaller frontier to minimize the number of candidates examined. Name the b^(d/2) vs b^d tradeoff explicitly.

Common mistakes

  • Not checking wordSet.has(endWord) upfront — if endWord isn't in the dictionary, return 0 immediately.
  • Not using a visited set — BFS without it revisits nodes exponentially.
  • Returning steps instead of steps+1 — you start at step 1 (beginWord counts as word #1 in the sequence).
  • Generating neighbors by comparing all pairs in the dictionary — O(N^2 * L) vs the O(M * 26) substitution approach.

Follow-up questions

An interviewer at AMD may pivot to one of these next:

  • Word Ladder II (LC 126) — return all shortest transformation sequences (backtracking from BFS parent map).
  • How does bidirectional BFS generalize to other shortest-path problems on implicit graphs?
  • Design a configuration-space search for finding the minimum ISA instruction substitution to reach a target encoding.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

FAQ

Why try all 26 letter substitutions instead of comparing word pairs in the dictionary?

Comparing all pairs is O(N^2 * L). Substituting each position with each of 26 letters is O(M * 26) per word, then checking membership in the Set is O(M) — overall O(M^2 * N) vs O(N^2 * L).

Why does bidirectional BFS help?

Standard BFS explores O(b^d) nodes. Bidirectional explores two frontiers of depth d/2, totaling O(b^(d/2)) nodes — exponentially fewer for large d.

Practice these live with InterviewChamp.AI

Drill Word Ladder and other AMD interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →