Skip to content

122 — Word Ladder

Jump to bottom
rebeloper edited this page Jul 14, 2026 · 4 revisions

122 — Word Ladder

LeetCode 127 · Hard. Given beginWord, endWord, and a wordList, return the length of the shortest transformation sequence from beginWord to endWord, changing exactly one letter at a time, where every intermediate word must exist in wordList. Return 0 if no such sequence exists.

🍽️ Intuition

Every word is a node; an edge connects two words if they differ by exactly one letter. "Shortest transformation sequence" is then just "shortest path" in that implicit graph — and shortest path in an unweighted graph is BFS's entire reason for existing. The graph is never built explicitly as an adjacency list up front; instead, a word's neighbors are discovered on demand by figuring out which other words in the list are one letter away. The whole difficulty of this problem is making "find this word's neighbors" cheap, since doing it carelessly turns an otherwise-standard BFS into something much slower.

🚩 Pattern-Recognition Cue

"Shortest sequence of one-letter transformations between two words, through a dictionary" is the cue for BFS on an implicit graph where words are nodes and "differs by one letter" is the edge rule — the only design decision left is how cheaply that edge rule can be checked.

🐢 Brute Force

BFS is structured correctly, but a word's neighbors are found by scanning the entire word list and comparing every candidate character by character to check for a one-letter difference.

func ladderLengthBruteForce(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
    let words = Array(wordList)
    guard words.contains(endWord) else { return 0 }

    func differsByOne(_ a: [Character], _ b: [Character]) -> Bool {
        guard a.count == b.count else { return false }
        var diffCount = 0
        for i in 0..<a.count {
            if a[i] != b[i] {
                diffCount += 1
                if diffCount > 1 { return false }
            }
        }
        return diffCount == 1
    }

    var queue: [[Character]] = [Array(beginWord)]
    var visited: Set<String> = [beginWord]
    var steps = 1
    var head = 0

    while head < queue.count {
        let levelSize = queue.count - head
        for _ in 0..<levelSize {
            let current = queue[head]
            head += 1
            if String(current) == endWord { return steps }
            // Rescan the ENTIRE word list looking for one-letter-different words.
            for candidate in words {
                guard !visited.contains(candidate) else { continue }
                if differsByOne(current, Array(candidate)) {
                    visited.insert(candidate)
                    queue.append(Array(candidate))
                }
            }
        }
        steps += 1
    }

    return 0
}

Big-O: O(N² · L) — for each of up to N words dequeued, the entire word list (N words) is rescanned, each comparison costing O(L) for a word of length L.

🚀 Optimal

Precompute, once, a dictionary from wildcard pattern (e.g. "h*t" for "hot") to every word matching that pattern. Then a word's neighbors are found by generating its L wildcard patterns and looking each one up — an O(1) dictionary access instead of an O(N) scan.

func ladderLength(_ beginWord: String, _ endWord: String, _ wordList: [String]) -> Int {
    guard wordList.contains(endWord) else { return 0 }

    var patternBuckets: [String: [String]] = [:]

    func patterns(for word: String) -> [String] {
        var chars = Array(word)
        var result: [String] = []
        for i in 0..<chars.count {
            let original = chars[i]
            chars[i] = "*"
            result.append(String(chars))
            chars[i] = original
        }
        return result
    }

    for word in wordList {
        for pattern in patterns(for: word) {
            patternBuckets[pattern, default: []].append(word)
        }
    }

    var visited: Set<String> = [beginWord]
    var queue: [String] = [beginWord]
    var steps = 1
    var head = 0

    while head < queue.count {
        let levelSize = queue.count - head
        for _ in 0..<levelSize {
            let current = queue[head]
            head += 1
            if current == endWord { return steps }
            for pattern in patterns(for: current) {
                for neighbor in patternBuckets[pattern, default: []] {
                    guard !visited.contains(neighbor) else { continue }
                    visited.insert(neighbor)
                    queue.append(neighbor)
                }
            }
        }
        steps += 1
    }

    return 0
}

// smoke test
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log","cog"]))  // 5
print(ladderLength("hit", "cog", ["hot","dot","dog","lot","log"]))        // 0 - cog not in list

Big-O: O(N · L²) time — building patternBuckets costs O(N · L) (each of N words generates L patterns of length L), and each BFS step generates L patterns per word, each a O(L) dictionary lookup. O(N · L) space for the buckets.

🔑 The Key Insight

The brute force answers "which words are one letter away from this one?" the expensive way — by comparing this word against every other word in the list, one character at a time. The optimal version flips that lookup around entirely: rather than comparing words to each other, it groups words by the "shape" they share once one letter is blanked out ("h*t" groups "hot", "hat", "hit", ...). Two words are neighbors exactly when they land in the same bucket for some blanked position — so finding a word's neighbors becomes "generate my L patterns, look each one up," trading an O(N) comparison against the whole list for an O(1) dictionary access per pattern. Same BFS, same shortest-path guarantee — just a dramatically cheaper way of answering "who are my neighbors?"

🔗 Related Chapters

  • Graphs — words and one-letter-difference edges form exactly the kind of implicit, non-hierarchical graph that chapter frames as "connections in every direction, discovered on demand."
  • BFS — BFS's shortest-path guarantee in an unweighted graph is the entire reason this problem reduces to a BFS, rather than DFS or anything else.
  • Hash Maps and Hash Sets — patternBuckets and visited are both dictionaries/sets doing the heavy lifting: O(1) neighbor lookup and O(1) visited checks, respectively.

🧸 Memory Sentence

Word Ladder is BFS on words instead of numbers — build wildcard-pattern buckets once so a word's neighbors are a dictionary lookup, not a full rescan of every other word in the list.

✅ Check Your Understanding

  1. Why do two words landing in the same wildcard-pattern bucket (like "hot" and "hit" both matching "h*t") guarantee they differ by exactly one letter — and not, say, zero or two letters?
  2. steps starts at 1 rather than 0. Trace through the first iteration of the while loop for ladderLength("hit", "hit", ["hit"]) — what does the function return, and why does starting at 1 make that correct?
  3. Why does building patternBuckets once, up front, cost O(N · L) total, rather than O(N · L) per BFS step the way the brute force's per-step rescan does?

⬅️ Previous: Graph Valid Tree · Next: Reconstruct Itinerary ➡️

Clone this wiki locally