Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Hardgrid-graph-bfs

Word Ladder

Problem (restated)

Given beginWord, endWord, and a word list, return the length of the shortest transformation sequence from begin to end, changing one letter at a time, each intermediate word in the list. Return 0 if impossible.

Intuition

Implicit graph: words are nodes; edge if Hamming distance 1. BFS from begin finds shortest sequence length (count words).

Approaches

BFS on word graph

Unverified

Time O(N * L * 26)Space O(N)

Idea. Queue of (word, dist). For each position try a-z neighbors present in the set; remove when visiting.

Walkthrough. hit → hot → dot → dog → cog has length 5.

Trade-offs. BFS optimal for unweighted; bidirectional BFS is faster in practice.

Solution

export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q: [string, number][] = [[beginWord, 1]];
  const seen = new Set<string>([beginWord]);
  while (q.length) {
    const [w, d] = q.shift()!;
    if (w === endWord) return d;
    const arr = w.split("");
    for (let i = 0; i < arr.length; i++) {
      const orig = arr[i]!;
      for (let c = 97; c <= 122; c++) {
        arr[i] = String.fromCharCode(c);
        const next = arr.join("");
        if (set.has(next) && !seen.has(next)) {
          seen.add(next);
          q.push([next, d + 1]);
        }
      }
      arr[i] = orig;
    }
  }
  return 0;
}

export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const set = new Set(wordList);
  if (!set.has(endWord)) return 0;
  const q: [string, number][] = [[beginWord, 1]];
  const seen = new Set<string>([beginWord]);
  while (q.length) {
    const [w, d] = q.shift()!;
    if (w === endWord) return d;
    const arr = w.split("");
    for (let i = 0; i < arr.length; i++) {
      const orig = arr[i]!;
      for (let c = 97; c <= 122; c++) {
        arr[i] = String.fromCharCode(c);
        const next = arr.join("");
        if (set.has(next) && !seen.has(next)) {
          seen.add(next);
          q.push([next, d + 1]);
        }
      }
      arr[i] = orig;
    }
  }
  return 0;
}

Template connection

Graph BFS on implicit adjacency.

Deep dive

Build the graph implicitly: from a word, try all one-letter mutations and keep those in the word set. BFS from beginWord guarantees the first time you reach endWord is the shortest ladder. Count words in the path (begin counts as 1). Mark visited when enqueueing so the same word is not expanded twice. Bidirectional BFS (search from both ends) is a common constant-factor speedup on large dictionaries.

Bidirectional BFS

Unverified

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

Idea. Grow two frontiers from begin and end; expand the smaller side each step. Meeting means shortest ladder.

Trade-offs. Same worst-case class as one-way BFS; often fewer expansions on wide dictionaries.

Solution

/** Bidirectional BFS on the word graph, meet in the middle. */
export function ladderLengthBi(beginWord: string, endWord: string, wordList: string[]): number {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let dist = 1;
  const neighbors = (w: string): string[] => {
    const out: string[] = [];
    const a = w.split("");
    for (let i = 0; i < a.length; i++) {
      const o = a[i]!;
      for (let c = 97; c <= 122; c++) {
        a[i] = String.fromCharCode(c);
        const n = a.join("");
        if (dict.has(n)) out.push(n);
      }
      a[i] = o;
    }
    return out;
  };
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set<string>();
    for (const w of front) {
      for (const n of neighbors(w)) {
        if (back.has(n)) return dist + 1;
        if (!seen.has(n)) {
          seen.add(n);
          next.add(n);
        }
      }
    }
    front = next;
    dist++;
  }
  return 0;
}

/** Bidirectional BFS on the word graph, meet in the middle. */
export function ladderLengthBi(beginWord: string, endWord: string, wordList: string[]): number {
  const dict = new Set(wordList);
  if (!dict.has(endWord)) return 0;
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  const seen = new Set<string>([beginWord, endWord]);
  let dist = 1;
  const neighbors = (w: string): string[] => {
    const out: string[] = [];
    const a = w.split("");
    for (let i = 0; i < a.length; i++) {
      const o = a[i]!;
      for (let c = 97; c <= 122; c++) {
        a[i] = String.fromCharCode(c);
        const n = a.join("");
        if (dict.has(n)) out.push(n);
      }
      a[i] = o;
    }
    return out;
  };
  while (front.size && back.size) {
    if (front.size > back.size) [front, back] = [back, front];
    const next = new Set<string>();
    for (const w of front) {
      for (const n of neighbors(w)) {
        if (back.has(n)) return dist + 1;
        if (!seen.has(n)) {
          seen.add(n);
          next.add(n);
        }
      }
    }
    front = next;
    dist++;
  }
  return 0;
}

Reflection

An edge is a one-letter change. The first time BFS reaches the word, that path is shortest. DFS does not give you the shortest.
beginWord may be missing from the list. A missing endWord returns 0. A word you have already queued must not enter again.
Trying 26 substitutions is cheaper than scanning the whole dictionary. Bidirectional BFS returns the same length and visits fewer words.