Interview OS
Back to Coding Prep

Coding

Word Ladder

BFS/DFS · Hard

BFS/DFSHard

Overview

Word Ladder: transform one word into another changing a single letter at a time, staying within a dictionary. Words one letter apart form graph edges, so BFS finds the shortest transformation length level by level.

How it works

BFS/DFS
InputGraphBFSOutputbegin,end,dictwordsNeighbors*_ patternLevel orderqueueLadder length
ClientDataAsyncEdge

Step by step, with examples

  1. 1

    begin,end,dict

    • Shortest one-letter transform chain.
  2. 2

    Neighbors

    • Words one letter apart are edges.
  3. 3

    Level order

    • Expand by one edit per level.
  4. 4

    Ladder length

    • Return the number of steps.
    • Example: hit → cog = 5

Problem

Given begin/end words and a word list, return the length of the shortest transformation sequence changing one letter at a time.

Approach

  • Treat words as graph nodes, edges between one-letter neighbors
  • BFS level by level for the shortest path

Solution

function ladderLength(begin, end, wordList) {
  const words = new Set(wordList);
  if (!words.has(end)) return 0;
  let queue = [begin], steps = 1;
  while (queue.length) {
    const next = [];
    for (const w of queue) {
      if (w === end) return steps;
      for (let i = 0; i < w.length; i++)
        for (let c = 97; c < 123; c++) {
          const cand = w.slice(0,i) + String.fromCharCode(c) + w.slice(i+1);
          if (words.has(cand)) { words.delete(cand); next.push(cand); }
        }
    }
    queue = next; steps++;
  }
  return 0;
}

Complexity

Time O(N · L · 26), Space O(N · L).

Where this content comes from

For full transparency, this content is curated and verified from these sources:

Curated company-tagged problem banksRecurring interview pattern librariesOppZen-authored drills & solutions