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

Tested only

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

Tested only

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

Which pattern gave this away within 90 seconds?
What changed from the standard template?
What would break the current solution?