Skip to main content

127. Word Ladder

hardAsked at Gusto

Find the shortest transformation sequence from beginWord to endWord changing one letter at a time. Gusto asks this to test BFS on implicit graphs — the graph is never explicitly built, and the neighbour-generation step (26 letter substitutions) is where candidates get bogged down without a clear strategy.

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

Source citations

Public interview reports confirming this problem appears in Gusto loops.

  • Glassdoor (2025-09)— Reported in Gusto staff-engineer onsite reports as a hard graph problem testing BFS on word transformation graphs.
  • Blind (2025-07)— Gusto threads cite Word Ladder as a rare but high-signal hard problem used in senior and staff SWE loops.

Problem

A transformation sequence from word beginWord to word endWord using a dictionary wordList is a sequence beginWord → s1 → s2 → ... → sk such that: every consecutive pair of words differs by a single letter, every si for 1 ≤ i ≤ k is in wordList, and sk == endWord. 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: hit → hot → dot → dog → cog (5 words in the path).

Example 2

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

Explanation: 'cog' is not in the word list — no path exists.

Approaches

1. BFS on implicit word graph

Use BFS where each node is a word and edges connect words differing by one letter. Level = sequence length. Stop when endWord is reached.

Time
O(M² × N) where M is word length and N is wordList size
Space
O(M² × 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, length] = queue.shift();
    for (let i = 0; i < word.length; i++) {
      for (let c = 0; c < 26; c++) {
        const newChar = String.fromCharCode(97 + c);
        if (newChar === word[i]) continue;
        const newWord = word.slice(0, i) + newChar + word.slice(i + 1);
        if (newWord === endWord) return length + 1;
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          visited.add(newWord);
          queue.push([newWord, length + 1]);
        }
      }
    }
  }
  return 0;
}

Tradeoff: O(M² × N) time. BFS guarantees shortest path. The neighbour-generation loop (26 × M substitutions per word) is the core of the algorithm. Adding to visited before enqueuing prevents re-processing.

2. Bidirectional BFS

Run BFS simultaneously from both beginWord and endWord. Expand the smaller frontier each step. When the two frontiers meet, the path is found in roughly half the steps.

Time
O(M² × N) but roughly half the branching factor in practice
Space
O(M² × N)
function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) return 0;
  let beginSet = new Set([beginWord]);
  let endSet = new Set([endWord]);
  const visited = new Set();
  let length = 1;
  while (beginSet.size && endSet.size) {
    // always expand the smaller frontier
    if (beginSet.size > endSet.size) [beginSet, endSet] = [endSet, beginSet];
    const nextSet = new Set();
    for (const word of beginSet) {
      for (let i = 0; i < word.length; i++) {
        for (let c = 0; c < 26; c++) {
          const newWord = word.slice(0, i) + String.fromCharCode(97 + c) + word.slice(i + 1);
          if (endSet.has(newWord)) return length + 1;
          if (wordSet.has(newWord) && !visited.has(newWord)) {
            visited.add(newWord);
            nextSet.add(newWord);
          }
        }
      }
    }
    beginSet = nextSet;
    length++;
  }
  return 0;
}

Tradeoff: Same asymptotic complexity but dramatically faster in practice — the frontier grows like b^(d/2) from each side rather than b^d total. Worth mentioning as a follow-up optimisation.

Gusto-specific tips

The key question Gusto interviewers ask is: 'How do you efficiently find all valid neighbours of a word?' Walk through the 26 × M substitution loop before coding. Also explain why BFS is correct here (guarantees shortest path) vs DFS (would need backtracking and doesn't guarantee shortest path). Bidirectional BFS is an impressive follow-up — mention it proactively if time allows.

Common mistakes

  • Adding a word to visited after dequeuing rather than before enqueuing — allows multiple insertions of the same word, causing TLE.
  • Not checking if endWord is in wordList at the start — saves unnecessary BFS work.
  • Using string comparison inside the neighbour loop instead of checking against the wordSet — O(M) comparison is fine but comparing against all N words is O(MN) per step.
  • Returning length instead of length + 1 on finding endWord — the count includes both beginWord and endWord.

Follow-up questions

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

  • Word Ladder II (LC 126) — return all shortest transformation sequences.
  • What if multiple source words are given as starting points?
  • How does bidirectional BFS change the complexity in theory vs in practice?

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 use BFS rather than DFS for this problem?

BFS explores nodes level-by-level, guaranteeing that the first time endWord is reached it's via the shortest path. DFS would find some path but not necessarily the shortest.

Why is beginWord added to visited immediately?

To prevent cycles — without marking beginWord as visited, a neighbour of beginWord could generate beginWord again on the next level.

What if beginWord itself is in the wordList?

It doesn't matter for the algorithm — beginWord is always the starting node regardless. The wordSet is only used for neighbour validation.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →