# Word Ladder

- **Canonical ID**: `word-ladder`
- **Canonical URL**: https://dsacheatsheet.com/problems/word-ladder
- **Difficulty**: hard
- **Patterns**: Graphs
- **Version**: 1.0.0 (verified 2026-11-11T21:20:00Z)
- **Original Problem**: https://leetcode.com/problems/word-ladder/

## 1. Core Invariant / The Trick

Avoid O(N^2 * L) pairwise comparisons by indexing dictionary words onto wildcard patterns (`h*t -> ["hot", "hit"]`), or run **bidirectional BFS** generating 26 char substitutions per position on the smaller frontier.

## 2. Complexity Bounds & Proof

- **Time Complexity**: `O(N * L^2)`
- **Space Complexity**: `O(N * L)`
- **Proof**: Wait: with wordSet lookup over L indices × 26 chars, generating next words runs in O(L^2 * 26) per word instead of scanning N words.

## 3. Minimal Idiomatic Code

### Python
```python
def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    words = set(wordList)
    if endWord not in words:
        return 0
    front, back = {beginWord}, {endWord}
    words.discard(beginWord)
    steps = 1
    while front and back:
        if len(front) > len(back):
            front, back = back, front
        nxt = set()
        for w in front:
            for i in range(len(w)):
                for ch in 'abcdefghijklmnopqrstuvwxyz':
                    cand = w[:i] + ch + w[i + 1:]
                    if cand in back:
                        return steps + 1
                    if cand in words:
                        words.remove(cand)
                        nxt.add(cand)
        front = nxt
        steps += 1
    return 0
```

### TypeScript
```typescript
export function ladderLength(beginWord: string, endWord: string, wordList: string[]): number {
  const words = new Set(wordList);
  if (!words.has(endWord)) return 0;
  let front = new Set<string>([beginWord]);
  let back = new Set<string>([endWord]);
  words.delete(beginWord);
  let steps = 1;
  while (front.size > 0 && back.size > 0) {
    if (front.size > back.size) [front, back] = [back, front];
    const nxt = new Set<string>();
    for (const w of front) {
      for (let i = 0; i < w.length; i++) {
        for (let c = 97; c <= 122; c++) {
          const cand = w.slice(0, i) + String.fromCharCode(c) + w.slice(i + 1);
          if (back.has(cand)) return steps + 1;
          if (words.has(cand)) {
            words.delete(cand);
            nxt.add(cand);
          }
        }
      }
    }
    front = nxt;
    steps++;
  }
  return 0;
}
```

### C++
```cpp
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> words(wordList.begin(), wordList.end());
    if (!words.count(endWord)) return 0;
    unordered_set<string> front{beginWord}, back{endWord};
    int steps = 1;
    while (!front.empty() && !back.empty()) {
        if (front.size() > back.size()) swap(front, back);
        unordered_set<string> nxt;
        for (string w : front) {
            for (size_t i = 0; i < w.size(); ++i) {
                char orig = w[i];
                for (char c = 'a'; c <= 'z'; ++c) {
                    w[i] = c;
                    if (back.count(w)) return steps + 1;
                    if (words.erase(w)) nxt.insert(w);
                }
                w[i] = orig;
            }
        }
        front = move(nxt); steps++;
    }
    return 0;
}
```

### Java
```java
int ladderLength(String beginWord, String endWord, List<String> wordList) {
    Set<String> words = new HashSet<>(wordList);
    if (!words.contains(endWord)) return 0;
    Set<String> front = new HashSet<>(List.of(beginWord)), back = new HashSet<>(List.of(endWord));
    int steps = 1;
    while (!front.isEmpty() && !back.isEmpty()) {
        if (front.size() > back.size()) { var t = front; front = back; back = t; }
        Set<String> nxt = new HashSet<>();
        for (String w : front) {
            char[] arr = w.toCharArray();
            for (int i = 0; i < arr.length; i++) {
                char orig = arr[i];
                for (char c = 'a'; c <= 'z'; c++) {
                    arr[i] = c;
                    String cand = new String(arr);
                    if (back.contains(cand)) return steps + 1;
                    if (words.remove(cand)) nxt.add(cand);
                }
                arr[i] = orig;
            }
        }
        front = nxt; steps++;
    }
    return 0;
}
```

### Go
```go
func ladderLength(beginWord, endWord string, wordList []string) int {
    words := make(map[string]bool, len(wordList))
    for _, w := range wordList { words[w] = true }
    if !words[endWord] { return 0 }
    front, back := map[string]bool{beginWord: true}, map[string]bool{endWord: true}
    steps := 1
    for len(front) > 0 && len(back) > 0 {
        if len(front) > len(back) { front, back = back, front }
        nxt := map[string]bool{}
        for w := range front {
            b := []byte(w)
            for i := range b {
                orig := b[i]
                for c := byte('a'); c <= 'z'; c++ {
                    b[i] = c; s := string(b)
                    if back[s] { return steps + 1 }
                    if words[s] { delete(words, s); nxt[s] = true }
                }
                b[i] = orig
            }
        }
        front = nxt; steps++
    }
    return 0
}
```

## 4. Failure Modes & Interview Follow-ups

### Pitfalls
- Returning edge distance instead of word count (`beginWord` counts as step `1`).
- Checking `endWord not in wordSet` early avoids redundant graph expansion.

### Follow-ups
- Word Ladder II stores parent DAGs per BFS level and backtracks all shortest paths.