Skip to main content

127. Word Ladder

hardAsked at Google

Given a begin word, end word, and word list, return the length of the shortest transformation sequence where each step changes one letter. Google asks this to test whether you reach for BFS on an implicit graph and can articulate why BFS (not DFS) is the right tool for shortest-path on unweighted edges.

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

Source citations

Public interview reports confirming this problem appears in Google loops.

  • Glassdoor (2026-Q1)— Google L4 onsite reports cite this as the graph round.
  • Blind (2025-09)— Recurring Google interview problem.

Problem

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

Explanation: One shortest transformation: "hit" -> "hot" -> "dot" -> "dog" -> "cog", length 5.

Example 2

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

Explanation: endWord not in word list.

Approaches

1. BFS with neighbor enumeration

Standard BFS. For each word, try replacing every position with a-z to get neighbors. Check membership in the dictionary set.

Time
O(N * L * 26)
Space
O(N * L)
function ladderLength(beginWord, endWord, wordList) {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q = [[beginWord, 1]];
  const seen = new Set([beginWord]);
  while (q.length) {
    const [word, dist] = q.shift();
    if (word === endWord) return dist;
    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 (set.has(next) && !seen.has(next)) {
          seen.add(next);
          q.push([next, dist + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: Straightforward BFS with enumerated neighbors. The 26-letter inner loop is the constant factor.

2. Bidirectional BFS (optimal)

BFS from both ends simultaneously, swapping to expand the smaller frontier. Meet in the middle.

Time
O(N * L * 26)
Space
O(N * L)
function ladderLengthBi(beginWord, endWord, wordList) {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  let beginSet = new Set([beginWord]);
  let endSet = new Set([endWord]);
  const visited = new Set();
  let dist = 1;
  while (beginSet.size && endSet.size) {
    if (beginSet.size > endSet.size) [beginSet, endSet] = [endSet, beginSet];
    const next = new Set();
    for (const word of beginSet) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const cand = word.slice(0, i) + String.fromCharCode(c) + word.slice(i + 1);
          if (endSet.has(cand)) return dist + 1;
          if (set.has(cand) && !visited.has(cand)) {
            visited.add(cand);
            next.add(cand);
          }
        }
      }
    }
    beginSet = next;
    dist++;
  }
  return 0;
}

Tradeoff: Bidirectional BFS halves the effective depth — typically 100-1000x faster on dense word lists. Same asymptotic complexity but dramatically better constant.

Google-specific tips

Google interviewers want you to articulate why BFS (not DFS) is the right tool: BFS guarantees the shortest path on unweighted graphs. Then, if you want to score higher, mention bidirectional BFS as the practical optimization. State out loud: 'Searching from both ends meets in the middle, which can be exponentially faster on branchy graphs.'

Common mistakes

  • Building an explicit adjacency list — wasteful at L*26 per word, just enumerate neighbors on the fly.
  • Using DFS — works but doesn't give shortest path without extra bookkeeping.
  • Forgetting to check endWord existence in the word list upfront.

Follow-up questions

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

  • Word Ladder II (LC 126): return all shortest paths.
  • What if some edges have higher 'cost' (weighted)?
  • What if the alphabet is much larger than 26 (e.g., Unicode)?

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?

BFS explores by distance — the first time we visit endWord, the distance is the shortest. DFS could find a longer path first and need extra logic to track the minimum.

Is bidirectional BFS worth it in an interview?

Often yes — Google interviewers like the optimization. Mention it after the standard BFS solution. If you have time, implement it. If not, articulating it scores nearly as well.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →