127. Word Ladder

hardAsked at Anduril

Find the shortest transformation sequence from one word to another by changing one letter at a time. Anduril asks this to test BFS shortest-path reasoning on an implicit graph — the ability to model a state-space as a graph and apply BFS for shortest paths is fundamental to route planning and state-space search in autonomous systems.

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

Source citations

Public interview reports confirming this problem appears in Anduril loops.

Glassdoor (2025-11)— Anduril SWE senior onsite reports mention Word Ladder as a BFS/state-space hard question.
Blind (2025-09)— Anduril threads describe BFS shortest-path problems including Word Ladder as appearing in algorithmic-depth 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 exactly one letter, every si for 1 <= i <= k is in wordList, and sk == endWord. Given beginWord, endWord, and wordList, return the number of words in the shortest transformation sequence from beginWord to endWord, 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

Explanation: hit -> hot -> dot -> dog -> cog. Length = 5.

Example 2

Input

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

Output

Explanation: 'cog' is not in the word list; no valid sequence exists.

Approaches

1. BFS with neighbor generation

Model words as graph nodes. Two words are adjacent if they differ by exactly one letter. BFS from beginWord; return level count when endWord is reached.

Time: O(M^2 * N) where M is word length, N is 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]]; // [word, level]
  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++) { // 'a' to 'z'
        const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
        if (newWord === endWord) return level + 1;
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, level + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: O(M^2 * N) time. Generating all M*26 neighbors per word and checking membership in the set is the key step. queue.shift() is O(n) for arrays — mention using a proper queue (pointer-based) for production code.

2. Bidirectional BFS

Run BFS simultaneously from beginWord and endWord. At each step, expand the smaller frontier. Stop when the frontiers meet.

Time: O(M^2 * N) but with much smaller constant due to frontier pruning
Space: O(M^2 * N)

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  let frontA = new Set([beginWord]);
  let frontB = new Set([endWord]);
  const visited = new Set([beginWord, endWord]);
  let level = 1;
  while (frontA.size && frontB.size) {
    if (frontA.size > frontB.size) [frontA, frontB] = [frontB, frontA];
    const nextFront = new Set();
    for (const word of frontA) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const newWord = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (frontB.has(newWord)) return level + 1;
          if (wordSet.has(newWord) && !visited.has(newWord)) {
            visited.add(newWord);
            nextFront.add(newWord);
          }
        }
      }
    }
    frontA = nextFront;
    level++;
  }
  return 0;
}

Tradeoff: Dramatically faster in practice by always expanding the smaller frontier. Reduces the effective branching factor. Anduril engineers are impressed when candidates know bidirectional BFS.

Anduril-specific tips

Lead with the problem modeling insight: 'This is an implicit graph — each word is a node, adjacent words differ by one character. BFS finds the shortest path.' Anduril engineers value this framing before any code. Then mention bidirectional BFS as an optimization: 'By running BFS from both ends and always expanding the smaller frontier, the search space grows as two smaller balls instead of one large one.' The implementation of bidirectional BFS is a strong differentiator at Anduril.

Common mistakes

Not checking if endWord is in the word list before starting BFS — return 0 immediately if it isn't.
Including beginWord in the visited set but then still trying to re-visit it — initialize visited with beginWord.
Returning level instead of level+1 when endWord is found as a neighbor — the path length includes both endpoints.
Using queue.shift() without noting its O(n) cost — in a production implementation, use a pointer or a proper queue data structure.

Follow-up questions

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

Word Ladder II (LC 126) — return all shortest transformation sequences.
How would you precompute all neighbor relationships to avoid repeated character substitution during BFS?
How does bidirectional BFS reduce the time complexity in practice for this specific problem?

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 BFS and not DFS for shortest path?

BFS explores nodes level by level, guaranteeing that the first time endWord is reached, it is via the shortest path. DFS explores deeply and may find a long path before a short one.

Why iterate over 26 characters instead of comparing against the word list?

Iterating 26*M substitutions per word and checking the set is O(26*M) per word. Comparing against all N words in the list is O(M*N) per word. For large dictionaries, the substitution approach is faster.

What is the time complexity with bidirectional BFS?

Same worst-case O(M^2 * N) but the effective constant is much smaller because the search tree is split into two trees of depth L/2 instead of one of depth L, reducing the branching-factor exponent.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →