Word Ladder (LC 127)

Problem Statement

Given two words beginWord and endWord and a word list wordList, return the length of the shortest transformation sequence from beginWord to endWord such that:

• Only one letter is changed per step.
• Each intermediate word must be in wordList.
• endWord must be in wordList.

Return 0 if no sequence exists. The length includes both endpoints.

Example 1:

Input:  beginWord = "hit", endWord = "cog",
        wordList = ["hot","dot","dog","lot","log","cog"]
Output: 5
Explanation: "hit" -> "hot" -> "dot" -> "dog" -> "cog".

Example 2:

Input:  beginWord = "hit", endWord = "cog",
        wordList = ["hot","dot","dog","lot","log"]
Output: 0

Constraints:

• 1 <= word.length <= 10 (letters lowercase)
• 1 <= wordList.length <= 5000

Difficulty: Hard

---

Pattern Recognition

• Input structure: word list acting as graph nodes; edges between words differing by exactly one letter.
• What are we computing? shortest path length.
• Pattern: BFS (unweighted shortest path).
• Why: BFS guarantees the first time you reach endWord, you do so in the minimum number of transformations.

The non-obvious part is constructing the graph efficiently. Naively comparing all pairs is O(N^2 * L). The trick: for each word, generate "pattern" keys by replacing each letter with *, and bucket words by these patterns.

---

Approach

Brute Force

Build the adjacency list by comparing every pair (O(N^2 * L)), then BFS. Works for small N, TLE when N = 5000.

Optimal — Pattern Buckets + BFS

Key Insight: Two words differ by exactly one letter if they share a pattern where one position is wildcarded. E.g., hot and dot both match *ot. Build a map pattern -> list of words.

Preprocessing:

patterns = {}
for word in wordList:
    for i in 0..len(word)-1:
        key = word[:i] + '*' + word[i+1:]
        patterns[key].append(word)

BFS:

queue = [(beginWord, 1)]
visited = {beginWord}
while queue:
    word, steps = queue.popleft()
    if word == endWord: return steps
    for i in 0..len(word)-1:
        key = word[:i] + '*' + word[i+1:]
        for next in patterns[key]:
            if next not in visited:
                visited.add(next)
                queue.append((next, steps + 1))
        patterns[key] = []   // optional: clear to avoid revisits
return 0

Time: O(N * L^2) — for each word, L patterns; each pattern string is L chars. BFS visits each word once. Space: O(N * L^2) for the pattern map.

Bidirectional BFS

Start BFS from both beginWord and endWord, alternate expanding the smaller frontier. Meets in the middle at roughly sqrt cost. Cuts the branching factor's exponent in half. Often 3-10x faster in practice.

---

Walkthrough

beginWord = "hit", endWord = "cog", list = ["hot","dot","dog","lot","log","cog"].

Pattern buckets (partial):

• *it: [hit]
• h*t: [hit, hot]
• hi*: [hit]
• *ot: [hot, dot, lot]
• h*t: above
• ho*: [hot]
• *og: [dog, log, cog]
• ...

BFS:

Queue front	Steps	Neighbors (new)	Added to queue
hit	1	hot	hot (2)
hot	2	dot, lot	dot (3), lot (3)
dot	3	dog	dog (4)
lot	3	log	log (4)
dog	4	cog — matches endWord	return 5

---

Implementation

TypeScript

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

    // Build pattern buckets
    const L = beginWord.length;
    const patterns = new Map<string, string[]>();
    const allWords = [beginWord, ...wordList];
    for (const word of allWords) {
        for (let i = 0; i < L; i++) {
            const key = word.substring(0, i) + '*' + word.substring(i + 1);
            if (!patterns.has(key)) patterns.set(key, []);
            patterns.get(key)!.push(word);
        }
    }

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

    while (queue.length > 0) {
        const [word, steps] = queue.shift()!;
        if (word === endWord) return steps;
        for (let i = 0; i < L; i++) {
            const key = word.substring(0, i) + '*' + word.substring(i + 1);
            for (const neighbor of patterns.get(key) || []) {
                if (!visited.has(neighbor)) {
                    visited.add(neighbor);
                    queue.push([neighbor, steps + 1]);
                }
            }
            patterns.set(key, []); // optional prune — avoids revisiting the bucket
        }
    }
    return 0;
}

C++

int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
    unordered_set<string> dict(wordList.begin(), wordList.end());
    if (!dict.count(endWord)) return 0;

    int L = beginWord.size();
    unordered_map<string, vector<string>> patterns;
    vector<string> allWords = wordList;
    allWords.push_back(beginWord);
    for (auto& word : allWords) {
        for (int i = 0; i < L; i++) {
            string key = word.substr(0, i) + "*" + word.substr(i + 1);
            patterns[key].push_back(word);
        }
    }

    queue<pair<string, int>> q;
    q.push({beginWord, 1});
    unordered_set<string> visited{beginWord};

    while (!q.empty()) {
        auto [word, steps] = q.front(); q.pop();
        if (word == endWord) return steps;
        for (int i = 0; i < L; i++) {
            string key = word.substr(0, i) + "*" + word.substr(i + 1);
            for (auto& neighbor : patterns[key]) {
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    q.push({neighbor, steps + 1});
                }
            }
            patterns[key].clear();
        }
    }
    return 0;
}

Watch out:

1. Forgetting to check whether endWord is in the dictionary up front lets you walk forever.
2. Using DFS here gives you a path, not the shortest. BFS only.
3. Not clearing pattern buckets after use is fine for correctness (visited set guards) but makes the inner loop O(N) worst case on degenerate inputs.

---

Complexity Analysis

	Time	Space
Brute Force (pair-compare)	O(N^2 * L)	O(N^2)
Pattern BFS	O(N * L^2)	O(N * L^2)
Bidirectional BFS	O(N * L^2) / 2	O(N * L^2)

Bottleneck: building pattern buckets dominates. With N = 5000, L = 10, that's 500,000 pattern strings of length 10 — completely tractable.

---

Edge Cases

1. endWord not in list — immediate return 0.
2. beginWord == endWord — usually problem guarantees they differ, but a check returning 1 is safe.
3. No path exists — BFS empties queue, return 0.
4. Very long word list with small alphabet — pattern buckets may be large; still O(N*L^2) total storage.
5. beginWord not in list — that is allowed; add it to the pattern bucket only if you want to use it as a source.
6. Cycle in graph — visited set prevents infinite loops.

---

Related Problems

• LC 126 — Word Ladder II — Return all shortest transformation sequences. BFS to compute distances, DFS to reconstruct.
• LC 433 — Minimum Genetic Mutation — Identical structure, bank of size 4 letters instead of 26.
• LC 752 — Open the Lock — Shortest path in a 4-digit combination graph; BFS with deadends.
• LC 773 — Sliding Puzzle — BFS on grid states; same shortest-path-on-implicit-graph pattern.

---

What Is Expected at Each Level

Junior: Recognize BFS as the unlock, build the adjacency by pairwise comparison, implement correctly for small inputs.

Mid-level: Use pattern buckets to avoid O(N^2), handle the endWord-missing edge case, state complexity correctly.

Senior (L4 target): Write bidirectional BFS, explain why it halves the exponent, handle Word Ladder II as a natural follow-up (distance map + DFS), and discuss when to switch representation (e.g., if the alphabet were size 26 and L much larger, generating all 25*L neighbors on the fly may beat the pattern-bucket approach).