127. Word Ladder

At a Glance

• Topic: graphs
• Pattern: BFS / shortest path on implicit graph
• Difficulty: Hard
• Companies: Amazon, Google, Meta, Microsoft, Bloomberg
• Frequency: Very High
• LeetCode: 127

Problem (one-liner)

Given two words beginWord and endWord, and a dictionary wordList, return the length of the shortest transformation sequence from beginWord to endWord where each step changes exactly one letter and every intermediate word must be in wordList. Return 0 if no sequence exists.

Recognition Cues

• Shortest sequence with unit-cost edges (one edit)
• Words as nodes; edges connect words differing by one letter
• Dictionary-sized graph — avoid building all pairwise edges explicitly

Diagram

At-a-glance flow (replace with problem-specific Mermaid as you refine this note). camelCase node IDs; no spaces in IDs.

Approaches

• Brute force — explore all edit paths with DFS — exponential — wrong for shortest unless bounded.
• BFS from start — layer-by-layer shortest path in unweighted graph — O(N * L^2) time (with adjacency-by-pattern trick O(N * L * 26) or bucket BFS) — optimal family.

Optimal Solution

Go

func ladderLength(beginWord string, endWord string, wordList []string) int {
	wordSet := make(map[string]struct{}, len(wordList)+1)
	for _, word := range wordList {
		wordSet[word] = struct{}{}
	}
	if _, exists := wordSet[endWord]; !exists {
		return 0
	}
	type queueItem struct {
		word   string
		length int
	}
	queue := []queueItem{{beginWord, 1}}
	visited := map[string]bool{beginWord: true}
	for len(queue) > 0 {
		current := queue[0]
		queue = queue[1:]
		if current.word == endWord {
			return current.length
		}
		runes := []rune(current.word)
		for index := range runes {
			original := runes[index]
			for letter := 'a'; letter <= 'z'; letter++ {
				if letter == original {
					continue
				}
				runes[index] = letter
				nextWord := string(runes)
				if _, inSet := wordSet[nextWord]; !inSet {
					continue
				}
				if visited[nextWord] {
					continue
				}
				visited[nextWord] = true
				queue = append(queue, queueItem{nextWord, current.length + 1})
			}
			runes[index] = original
		}
	}
	return 0
}

JavaScript

function ladderLength(beginWord, endWord, wordList) {
  const wordSet = new Set(wordList);
  if (!wordSet.has(endWord)) {
    return 0;
  }
  const queue = [{ word: beginWord, length: 1 }];
  const visited = new Set([beginWord]);
  while (queue.length > 0) {
    const current = queue.shift();
    if (current.word === endWord) {
      return current.length;
    }
    const chars = current.word.split('');
    for (let index = 0; index < chars.length; index += 1) {
      const original = chars[index];
      for (let code = 'a'.charCodeAt(0); code <= 'z'.charCodeAt(0); code += 1) {
        const letter = String.fromCharCode(code);
        if (letter === original) {
          continue;
        }
        chars[index] = letter;
        const nextWord = chars.join('');
        if (!wordSet.has(nextWord) || visited.has(nextWord)) {
          continue;
        }
        visited.add(nextWord);
        queue.push({ word: nextWord, length: current.length + 1 });
      }
      chars[index] = original;
    }
  }
  return 0;
}

Walkthrough

hit → dot → ... ; BFS explores distance 1 neighbors (one-letter flips present in set). First time endWord is dequeued, depth equals shortest ladder length.

Invariant: Queue holds words at nondecreasing distance from beginWord; BFS first hit on endWord is minimal.

Edge Cases

• endWord not in wordList — return 0 immediately
• beginWord == endWord — typically length 1 if allowed by statement (LeetCode: begin may not be in list; shortest path still counts begin as step 1)
• Dictionary size 1 — only if it connects
• No path — BFS exhausts queue

Pitfalls

• Using DFS for “shortest” without careful bounds — use BFS for unweighted shortest path
• Not marking visited before enqueue — duplicates inflate queue
• Building full graph all-pairs — too heavy; mutate letters or use pattern buckets

Similar Problems

• 994. Rotting Oranges — multi-source BFS on grid (Medium stepping stone)
• 200. Number of Islands — component / BFS-DFS on implicit graph (Medium)
• 778. Swim in Rising Water — shortest path with edge weights / threshold (Hard)

Variants

• Word Ladder II: track predecessors per layer; prune backward from endWord.
• Bidirectional BFS: alternate expansions from start and goal — cuts search space.
• Forbidden mutations: weighted edges or banned intermediate alphabet segments — Dijkstra if costs differ.

Mind-Map Tags

#bfs #implicit-graph #shortest-path #string-transform #layered-search