Graphs crash course ↗ · 101

127. Word Ladder

Find the shortest sequence of single-letter changes that transforms beginWord into endWord, using only words from a dictionary. The trick is treating each word as a graph node and running BFS — shortest path by construction — with wildcard-bucket adjacency to find neighbors in O(L) instead of O(N·L).

● HardBFSGraphHash MapTypeScript

PROBLEM What we're solving

Given beginWord, endWord, and a wordList, return the number of words in the shortest transformation sequence where each adjacent pair differs by exactly one letter and every intermediate word is in the list. If no such sequence exists, return 0.

Concrete example: beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"].
The shortest path is hit → hot → dot → dog → cog (5 words), so the answer is 5.

KEY IDEA Model as BFS on a word graph

Insight → every word is a graph node; two words share an edge when they differ by exactly one letter. The answer is the BFS depth at which we first reach endWord. BFS explores layer by layer, so the first time it touches the target is guaranteed to be the shortest path. The only hard part is finding neighbors efficiently — that's where wildcard buckets come in.

RECIPE Build buckets, then BFS level by level

0 · Early exit. If endWord is not in wordList, return 0immediately — we can never reach it.
1 · Build wildcard buckets. For every word and every position i, create the key word[0..i-1] + "*" + word[i+1..] and map it to all words that share that pattern. Example: "h*t" → ["hit", "hot"]. This lets us find all neighbors of a word in O(L) bucket lookups rather than scanning all N words.
2 · BFS with a visited set. Start with queue = [beginWord], depth = 1. Process one full BFS level per outer loop iteration (level-order BFS). For each word, try all L wildcard patterns, look up their buckets, and enqueue any unvisited neighbors.
3 · Return depth on first hit. The moment we encounter endWord as a neighbor, return the current depth + 1. BFS guarantees this is the minimum.
4 · Return 0 if queue empties. If BFS exhausts the reachable words without finding endWord, return 0.

Classic confusion → the problem asks for the length of the sequence (number of words, including beginWord and endWord), not the number of transformation steps. So initialize depth = 1 (counting beginWord) and increment at each BFS level. Many implementations start at 0 and get an off-by-one answer.

COST Complexity & alternatives

Naive: try every pair

O(N² · L)

Build the adjacency list by comparing all pairs — O(N²·L) preprocessing, then BFS.

Wildcard buckets + BFS

O(N · L²)

O(N·L) to build buckets (L keys per word, each key is L chars). BFS visits each word at most once: O(N·L) edges total. Overall O(N·L²).

Bidirectional BFS

For very large word lists, bidirectional BFS expands from both beginWord and endWord simultaneously, meeting in the middle. This reduces the search space from O(b^d) to O(b^(d/2)) where b = branching factor and d = depth. Same O(N·L²) worst-case preprocessing, but dramatically fewer nodes visited in practice.

Pattern transfer → the wildcard-bucket neighbor technique applies to Word Ladder II (all shortest paths), Minimum Genetic Mutation (same BFS on gene strings), and any problem asking for the shortest edit-distance path on a fixed alphabet. The BFS-over-implicit-graph pattern also appears in Jump Game IV (value buckets) and Open the Lock (digit patterns).

RUN IT BFS over words — each step changes one letter

begin =end =wordList =

step 0 / 15

STARTBuild wordSet from wordList. Early-exit if cog is not present. Seed queue with hit, mark it visited, start depth = 1.

1function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
2▶  const wordSet = new Set<string>(wordList);
3▶  if (!wordSet.has(endWord)) return 0;
4 
5  // Build wildcard buckets: "h*t" -> ["hit","hot"]
6  const buckets = new Map<string, string[]>();
7  for (const word of [beginWord, ...wordList]) {
8    for (let i = 0; i < word.length; i++) {
9      const key = word.slice(0, i) + '*' + word.slice(i + 1);
10      const list = buckets.get(key) ?? [];
11      list.push(word);
12      buckets.set(key, list);
13    }
14  }
15 
16▶  const visited = new Set<string>([beginWord]);
17▶  const queue: string[] = [beginWord];
18▶  let depth = 1;
19 
20  while (queue.length > 0) {
21    depth++;
22    const size = queue.length;
23    for (let qi = 0; qi < size; qi++) {
24      const word = queue.shift()!;
25      for (let i = 0; i < word.length; i++) {
26        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
27        for (const neighbor of buckets.get(pattern) ?? []) {
28          if (neighbor === endWord) return depth;
29          if (!visited.has(neighbor)) {
30            visited.add(neighbor);
31            queue.push(neighbor);
32          }
33        }
34      }
35    }
36  }
37 
38  return 0; // endWord unreachable
39}

queuehit

State

{hot, dot, dog, lot, log, cog}

wordSet

{hit}

visited

[hit]

queue

depth

current word / levelnewly enqueued / visitedword set / level sizeneighbor being checkedtarget found

slowfast

TYPESCRIPT The solution, annotated

wordLadder.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  // Build wildcard buckets: "h*t" -> ["hit","hot"]
  const buckets = new Map<string, string[]>();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      const list = buckets.get(key) ?? [];
      list.push(word);
      buckets.set(key, list);
    }
  }

  const visited = new Set<string>([beginWord]);
  const queue: string[] = [beginWord];
  let depth = 1;

  while (queue.length > 0) {
    depth++;
    const size = queue.length;
    for (let qi = 0; qi < size; qi++) {
      const word = queue.shift()!;
      for (let i = 0; i < word.length; i++) {
        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const neighbor of buckets.get(pattern) ?? []) {
          if (neighbor === endWord) return depth;
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return 0; // endWord unreachable
}

Reading it block by block

Lines 2–3 — early exit. Convert wordList to a Set<string> for O(1) membership checks, then immediately return 0 if endWordisn't present — no sequence can exist.

Lines 5–12 — build wildcard buckets. For each word (including beginWord) and each index i, create the key word[0..i-1] + "*" + word[i+1..]. Two words share a bucket entry iff they match at every position except i — exactly the one-letter-different criterion. This O(N·L²) preprocessing makes each BFS expansion O(L) instead of O(N·L).

Lines 14–16 — BFS initialization. Seed the queue with beginWord and mark it visited immediately (not when dequeued) to prevent duplicate enqueues. Start depth = 1 counting beginWord itself.

Lines 18–32 — level-by-level BFS. The outer while runs one BFS level per iteration. size = queue.length snapshots the current level boundary before we start adding the next one. Incrementing depth at the top of each outer loop counts words, not edges.

Lines 25–31 — neighbor expansion via buckets. For each dequeued word, try all L wildcard patterns. Looking up each bucket surfaces exactly the words reachable in one letter change. If a neighbor is endWord, return depth — BFS guarantees this is the shortest path. Otherwise, enqueue unvisited neighbors.

Line 37 — queue empty, return 0. If the while loop finishes without finding endWord, the word graph has no path from beginWord to endWord.

Complexity → O(N·L²) time: building buckets takes O(N·L) iterations, each creating a key of length L → O(N·L²) total. BFS visits each word at most once and tries O(L) patterns per word, with O(1) amortized bucket lookups → O(N·L) for BFS. Space: O(N·L²) for the bucket map.

INTERVIEWFollow-ups they'll ask

"Return all shortest transformation sequences (Word Ladder II)?" Run BFS tracking parents at each level (not just one), stop expanding past the first level that reaches endWord, then DFS-reconstruct all paths from the parent map.
"Can you use bidirectional BFS?" Maintain two frontiers — one from beginWord, one from endWord. Each iteration, expand the smaller frontier. When they meet, sum both depths. This is O(b^(d/2)) vs O(b^d) in practice.
"What if word lengths can differ?" Words of different lengths can never be one letter apart (by the problem definition), so you can partition by length and only BFS within each partition.
"What's the brute-force, and why is this better?" Naive builds an explicit adjacency list by comparing every pair: O(N²·L). The bucket approach preprocesses in O(N·L²) and finds neighbors in O(L) per word — critical when N is large and L is small.
"What if beginWord equals endWord?" Return 1 (the sequence is just the single word). Guard this before starting BFS.

OPTIMAL BFS

wordLadder.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  // Build wildcard buckets: "h*t" -> ["hit","hot"]
  const buckets = new Map<string, string[]>();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      const list = buckets.get(key) ?? [];
      list.push(word);
      buckets.set(key, list);
    }
  }

  const visited = new Set<string>([beginWord]);
  const queue: string[] = [beginWord];
  let depth = 1;

  while (queue.length > 0) {
    depth++;
    const size = queue.length;
    for (let qi = 0; qi < size; qi++) {
      const word = queue.shift()!;
      for (let i = 0; i < word.length; i++) {
        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const neighbor of buckets.get(pattern) ?? []) {
          if (neighbor === endWord) return depth;
          if (!visited.has(neighbor)) {
            visited.add(neighbor);
            queue.push(neighbor);
          }
        }
      }
    }
  }

  return 0; // endWord unreachable
}

ALT 1 Bidirectional BFS

O(N · L²) time · O(N · L²) space

Search from both beginWord and endWord at once, always expanding the smaller frontier and stopping the instant the two waves collide — far fewer nodes touched in practice.

approach-2.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  // Wildcard buckets: "h*t" -> ["hit","hot"], so neighbors cost O(L) to find.
  const buckets = new Map<string, string[]>();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      const list = buckets.get(key) ?? [];
      list.push(word);
      buckets.set(key, list);
    }
  }

  // Two frontiers, one growing from each end. 'seen' maps a word to which side
  // reached it, so a collision = a word already claimed by the OTHER side.
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let depth = 1;

  while (front.size > 0 && back.size > 0) {
    // Always expand the smaller frontier to keep the branching factor low.
    if (front.size > back.size) {
      const tmp = front;
      front = back;
      back = tmp;
    }

    depth++;
    const next = new Set<string>();
    for (const word of front) {
      for (let i = 0; i < word.length; i++) {
        const pattern = word.slice(0, i) + '*' + word.slice(i + 1);
        for (const neighbor of buckets.get(pattern) ?? []) {
          // If the other wave already owns this word, the paths meet here.
          if (back.has(neighbor)) return depth;
          if (!seen.has(neighbor)) {
            seen.add(neighbor);
            next.add(neighbor);
          }
        }
      }
    }
    front = next;
  }

  return 0; // frontiers never met -> unreachable
}

Note → The two searches meet at the midpoint, so the summed depth is exactly the optimal sequence length. Like the standard BFS this still requires endWord ∈ wordList — otherwise the back frontier can never touch a real word, handled by the early return.

ALT 2 Plain BFS — try all 26 letters

O(N · L · 26) time · O(N · L) space

Skip the bucket map entirely: at each position swap in every letter a–z and keep the candidates that exist in the word set.

approach-3.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  const visited = new Set<string>([beginWord]);
  let queue: string[] = [beginWord];
  let depth = 1;

  while (queue.length > 0) {
    depth++;
    const next: string[] = [];
    for (const word of queue) {
      // For each position, try substituting all 26 lowercase letters.
      for (let i = 0; i < word.length; i++) {
        for (let c = 97; c < 123; c++) {
          const ch = String.fromCharCode(c);
          if (ch === word[i]) continue; // same word, skip
          const candidate = word.slice(0, i) + ch + word.slice(i + 1);
          if (candidate === endWord) return depth;
          // Only follow candidates that are real dictionary words.
          if (wordSet.has(candidate) && !visited.has(candidate)) {
            visited.add(candidate);
            next.push(candidate);
          }
        }
      }
    }
    queue = next;
  }

  return 0; // endWord unreachable
}

Note → No preprocessing and tiny memory — only the visited set and the current level. The 26× factor is a constant, so this is competitive when L is small; it loses to the bucket map only because it probes letters that produce non-words.

ALT 3 Brute force — build the graph by comparing every pair

O(N² · L) time · O(N²) space

Skip the wildcard buckets and the 26-letter trick: compare every pair of words, link the two whenever they differ by exactly one letter, then run an ordinary BFS over that explicit adjacency list.

approach-4.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const words = [beginWord, ...wordList];
  if (!wordList.includes(endWord)) return 0;

  // Do two equal-length words differ in exactly one position?
  function oneApart(a: string, b: string): boolean {
    let diff = 0;
    for (let i = 0; i < a.length; i++) {
      if (a[i] !== b[i] && ++diff > 1) return false;
    }
    return diff === 1;
  }

  // Adjacency list built from all O(N²) pairwise comparisons.
  const adj = new Map<string, string[]>();
  for (const w of words) adj.set(w, []);
  for (let i = 0; i < words.length; i++) {
    for (let j = i + 1; j < words.length; j++) {
      if (oneApart(words[i], words[j])) {
        adj.get(words[i])!.push(words[j]);
        adj.get(words[j])!.push(words[i]);
      }
    }
  }

  const visited = new Set<string>([beginWord]);
  let queue: string[] = [beginWord];
  let depth = 1;
  while (queue.length > 0) {
    const next: string[] = [];
    for (const word of queue) {
      if (word === endWord) return depth;
      for (const nb of adj.get(word) ?? []) {
        if (!visited.has(nb)) {
          visited.add(nb);
          next.push(nb);
        }
      }
    }
    queue = next;
    depth++;
  }

  return 0; // endWord unreachable
}

Note → The BFS itself is fine; the cost is the up-front adjacency build, which compares all N² word pairs at O(L) each — O(N² · L) and quadratic memory. The wildcard-bucket version discovers neighbors in O(L) per word without ever materializing the full pairwise graph.

MNEMONIC The one-liner

"Swap each letter for a *, look up who shares that bucket, BFS level by level until the target pops out."

TRIGGERS When you see _ → reach for _

"shortest transformation sequence"	BFS on word graph
words differing by one character → neighbors	wildcard-bucket adjacency map
shortest path on an unweighted implicit graph	level-order BFS with visited set
"all shortest paths" variant	BFS + parent map + DFS reconstruction

SKELETON The reusable shape

skeleton.ts
function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const wordSet = new Set<string>(wordList);
  if (!wordSet.has(endWord)) return 0;

  // build wildcard buckets
  const buckets = new Map<string, string[]>();
  for (const word of [beginWord, ...wordList]) {
    for (let i = 0; i < word.length; i++) {
      const key = word.slice(0, i) + '*' + word.slice(i + 1);
      // bucket[key].push(word)
    }
  }

  const visited = new Set<string>([beginWord]);
  const queue: string[] = [beginWord];
  let depth = 1;

  while (queue.length > 0) {
    depth++;
    const size = queue.length;
    for (let qi = 0; qi < size; qi++) {
      const word = queue.shift()!;
      // try every wildcard pattern, look up bucket, enqueue unvisited neighbors
      // if neighbor === endWord return depth
    }
  }
  return 0;
}

FLASHCARDS Tap to flip

Why BFS instead of DFS for this problem?

BFS explores nodes level by level, so the first time it reaches endWord is guaranteed to be via the shortest path. DFS finds a path but not necessarily the shortest one.

tap to flip

1 / 7

Answer to reveal explanations. No penalty for retries.Score: 0 / 9

QUESTION 01

For beginWord="hit", endWord="cog", wordList=["hot","dot","dog","lot","log","cog"], what does ladderLength return?

QUESTION 02

What is the purpose of wildcard buckets (e.g. "h*t" → ["hit","hot"])?

QUESTION 03

Why must depth start at 1, not 0?

QUESTION 04

What is the time complexity of the wildcard-bucket BFS approach?

QUESTION 05

What should the function return if endWord is not in wordList?

QUESTION 06

Why mark a word as visited when it is enqueued rather than when it is dequeued?

QUESTION 07

For beginWord="hot", endWord="dog", wordList=["hot","dot","dog"], what is returned?

QUESTION 08

#127 · Word LadderBFS over words where neighbors differ by exactly one letter. Pre-build wildcard adjacency buckets ("h*t" → ["hot","hat"]) so each expansion is O(26×len). Return BFS depth as the transformation count.Which algorithmic approach does this primarily use?

QUESTION 09

PROBLEM What we're solving

KEY IDEA Model as BFS on a word graph

RECIPE Build buckets, then BFS level by level

COST Complexity & alternatives

Bidirectional BFS

RUN IT BFS over words — each step changes one letter

TYPESCRIPT The solution, annotated

Reading it block by block

INTERVIEWFollow-ups they'll ask

OPTIMAL BFS

ALT 1 Bidirectional BFS

ALT 2 Plain BFS — try all 26 letters

ALT 3 Brute force — build the graph by comparing every pair

MNEMONIC The one-liner

TRIGGERS When you see ___ → reach for ___

SKELETON The reusable shape

FLASHCARDS Tap to flip

TRIGGERS When you see _ → reach for _