Saturday, August 22, 2026

🔬 Saturday Deep Dive: Word Ladder — 双向 BFS 最短变换路径 (15 min read)

📊 NeetCode: 91/150 · SysDesign: 60/60 · Behavioral: 60/60 · Frontend: 37/50 · AI: 30/30

🔥 117-day streak!

🔗 LeetCode: https://leetcode.com/problems/word-ladder/

📹 NeetCode: https://neetcode.io/problems/word-ladder

Overview / 概述

中文： Word Ladder 是图遍历大章节的 Boss 关卡。给定起始词、目标词和词典，每次只能改变一个字母，且每个中间状态必须在词典中，问从起始词变换到目标词的最短步数。

表面上看是字符串题，但本质是一道最短路径题。每个单词是图中的节点，两个仅差一个字母的单词之间存在一条无向边。目标：从 beginWord 到 endWord 的最短边数。

这道题是 BFS 思维的终极考题，也是面试中双向 BFS（bidirectional BFS）最经典的应用场景。面试官出这道题，考的不只是"会 BFS"，而是你能不能主动提出优化并实现它。

English: Word Ladder is the Boss fight of the graph traversal chapter. Given a start word, end word, and dictionary, you can change exactly one letter per step — each intermediate word must be in the dictionary. Find the shortest transformation sequence length.

It looks like a string problem, but it's fundamentally a shortest path problem. Each word is a graph node; two words that differ by one letter share an undirected edge. Goal: shortest edge count from beginWord to endWord.

This is the ultimate BFS thinking test. The interview question isn't just "can you BFS?" — it's "can you proactively optimize to bidirectional BFS and implement it cleanly?"

Problem: Given beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"], return 5.

Part 1: Theory / 理论基础 (5 min)

为什么是 BFS？/ Why BFS?

中文： BFS 天然计算无权图的最短路径。它按层展开——第 1 层是所有距离为 1 的节点，第 2 层是所有距离为 2 的节点……一旦第一次到达终点，当前层数就是最短路径长度。DFS 不行：DFS 会探索更长的路径，无法保证第一次到达即最短。

English: BFS naturally computes shortest paths in unweighted graphs. It expands level by level — layer 1 = all nodes at distance 1, layer 2 = distance 2 … The moment you first reach the destination, the current layer is the shortest path. DFS won't work: it explores longer paths and can't guarantee first-arrival = shortest.

图建模 / Graph Model

每个单词 = 节点 (node)
两词差一字母 = 无向边 (undirected edge)
边权 = 1 (unweighted)

"hit" ——— "hot" ——— "dot" ——— "dog" ——— "cog"
                     |                    |
                    "lot" ——— "log" ———

朴素做法：每个单词对之间判断是否差一字母，构建邻接表。O(N² × L)，N 是词典大小，L 是单词长度。

双向 BFS 的直觉 / Bidirectional BFS Intuition

中文： 普通 BFS 从 beginWord 向外扩展。如果图的"分支因子"（branching factor）是 B，深度是 d，则搜索空间是 O(B^d)。

双向 BFS 的思路：同时从 beginWord 和 endWord 出发向中间扩展，两边相遇即停止。每边只搜索深度 d/2，总搜索空间 = O(2 × B^(d/2)) = O(B^(d/2))。

当 d 较大时，这是指数级的加速。

English: Regular BFS from beginWord explores O(B^d) nodes where B = branching factor, d = depth. Bidirectional BFS meets in the middle — each side explores depth d/2, giving O(2 × B^(d/2)) = O(B^(d/2)) nodes. Exponential speedup as d grows.

虚拟节点技巧 / Virtual Node Trick

中文： 判断两单词是否差一字母是 O(L²) 的操作（N 个词两两比较）。更快的方法：用通配符模式作为虚拟节点。

"hit" 对应三个虚拟节点："it", "ht", "hi"。所有匹配同一模式的单词（如 "hit" 和 "hot" 都匹配 "ht"）通过该虚拟节点相连。这将邻接表构建从 O(N²L) 降至 O(NL)。

English: Checking every word pair for one-letter difference is O(N²L). The virtual node trick: use wildcard patterns as intermediate nodes. "hit" maps to patterns "it", "ht", "hi". All words matching the same pattern (e.g., "hit" and "hot" both match "ht") are connected through that virtual node. Reduces adjacency construction from O(N²L) to O(NL).

Part 2: Step-by-Step Implementation / 一步一步实现 (8 min)

方法一：朴素 BFS / Approach 1: Basic BFS

时间复杂度 Time: O(N × L × 26) ≈ O(NL)

空间复杂度 Space: O(N × L)

from collections import deque

def ladderLength_basic(beginWord: str, endWord: str, wordList: list[str]) -> int:
    # Convert to set for O(1) lookup
    word_set = set(wordList)

    # endWord must be in dictionary
    if endWord not in word_set:
        return 0

    # BFS queue: (current_word, current_steps)
    # Start with beginWord, step count = 1 (beginWord itself counts)
    queue = deque([(beginWord, 1)])

    # Visited set: don't revisit words (avoids cycles)
    visited = {beginWord}

    while queue:
        word, steps = queue.popleft()

        # Try changing each position
        for i in range(len(word)):
            # Try all 26 possible letters
            for c in 'abcdefghijklmnopqrstuvwxyz':
                # Build the candidate by replacing position i
                candidate = word[:i] + c + word[i+1:]

                # Skip if same word or already visited
                if candidate == word or candidate in visited:
                    continue

                # Found endWord — this is the shortest path
                if candidate == endWord:
                    return steps + 1

                # Add to queue if in dictionary
                if candidate in word_set:
                    visited.add(candidate)
                    queue.append((candidate, steps + 1))

    # No path found
    return 0

关键洞察 / Key insight: We don't need to pre-build a graph. Generate neighbors on-the-fly by trying all 26-letter substitutions at each position. The word_set gives O(1) validity check.

方法二：双向 BFS / Approach 2: Bidirectional BFS ⭐ (面试亮点)

时间复杂度 Time: O(NL × 26) but with ~√ factor speedup in practice

空间复杂度 Space: O(N × L)

from collections import deque

def ladderLength(beginWord: str, endWord: str, wordList: list[str]) -> int:
    word_set = set(wordList)

    if endWord not in word_set:
        return 0

    # Two frontiers: one starting from beginWord, one from endWord
    # Each frontier is a SET (not queue) — we expand the SMALLER one each step
    front = {beginWord}   # frontier expanding from begin
    back  = {endWord}     # frontier expanding from end

    # Total steps taken (each iteration = 1 step from ONE side)
    steps = 1

    while front and back:
        # ALWAYS expand the smaller frontier — this is the key optimization
        # If we always pick the smaller side, we keep both sides balanced
        if len(front) > len(back):
            front, back = back, front

        # Generate next layer for the current frontier
        next_front = set()

        for word in front:
            for i in range(len(word)):
                for c in 'abcdefghijklmnopqrstuvwxyz':
                    candidate = word[:i] + c + word[i+1:]

                    # If this candidate appears in the OTHER frontier → MEET!
                    # We found a path: steps from front side + steps from back side
                    if candidate in back:
                        return steps + 1

                    # Only expand through valid dictionary words
                    if candidate in word_set:
                        next_front.add(candidate)

        # Move to next layer; remove visited words from word_set
        # (prevents re-visiting from the same side or infinite loops)
        word_set -= next_front
        front = next_front
        steps += 1

    # No path
    return 0

架构图 / Architecture Diagram:

Cross-check (Step 4 verification):

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

Tracing through the diagram vs code:

• Step 1: front={"hit"}, try all substitutions of "hit": h→a-z at pos 0 = "ait","bit"... none in dict; pos 1 = "hat","hbt"... none in dict; pos 2 = "hia","hib"... "hot" is in word_set ✓. next_front={"hot"}. "hot" in back={"cog"}? No. front={"hot"}, steps=2.
• Step 2: expand front={"hot"} (size 1 ≤ back size 1, same): from "hot": "dot","lot" in word_set. Neither in back. front={"dot","lot"}, steps=3.
• Step 3: len(front)=2 > len(back)=1 → swap! Now expanding back={"cog"}: "aog"..."log","dog" in word_set. Neither in swapped front={"dot","lot"}. back={"dog","log"}, steps=4.
• Step 4: len(front)=2 == len(back)=2 → expand front. From "dot": pos 2 change → "dog" in word_set → "dog" in back={"dog","log"}? YES! Return steps+1 = 5. ✅

Diagram matches code exactly.

方法三：虚拟节点 BFS / Approach 3: Virtual Node BFS

适合在面试中提及，理解其思路 / Good to mention in interviews as an insight:

from collections import defaultdict, deque

def ladderLength_virtual(beginWord: str, endWord: str, wordList: list[str]) -> int:
    # Build adjacency: pattern → list of words matching that pattern
    # "hit" → {"*it": ["hit",...], "h*t": ["hit","hot",...], "hi*": ["hit",...]}
    graph = defaultdict(list)

    for word in wordList + [beginWord]:
        for i in range(len(word)):
            # Wildcard pattern for position i
            pattern = word[:i] + '*' + word[i+1:]
            graph[pattern].append(word)

    # BFS on virtual graph: real words AND patterns as nodes
    queue = deque([(beginWord, 1)])
    visited = {beginWord}

    while queue:
        node, steps = queue.popleft()

        # Generate all patterns this word matches
        for i in range(len(node)):
            pattern = node[:i] + '*' + node[i+1:]

            # All words sharing this pattern are neighbors
            for neighbor in graph[pattern]:
                if neighbor == endWord:
                    return steps + 1
                if neighbor not in visited:
                    visited.add(neighbor)
                    queue.append((neighbor, steps + 1))

    return 0

复杂度对比 / Complexity Comparison

N = 词典大小, L = 单词长度

Part 3: Edge Cases & Gotchas / 边界情况 (2 min)

中文常见坑 / Common pitfalls:

1. endWord 不在词典中 / endWord not in wordList

if endWord not in word_set:
    return 0  # 别忘了这个检查！

这是最常见的 bug。beginWord 可以不在词典中（题目说明），但 endWord 必须在。

2. beginWord == endWord

# 题目保证 beginWord != endWord，但防御性编程：
if beginWord == endWord:
    return 1

3. 双向 BFS 中忘记交换 / Forgetting to swap in bidirectional BFS

# Wrong: always expand `front`
# Right:
if len(front) > len(back):
    front, back = back, front

如果忘记交换，退化成单向 BFS，失去所有优化优势。

4. 双向 BFS 的返回值 / Return value in bidirectional BFS

Meeting at step N means: we've taken N steps from the start side and are finding a match in the other frontier. The other frontier was already extended to cover those words. Return steps + 1.

• steps = number of layers expanded so far (from whichever side expanded each round)
• When we find a meeting point, we add 1 to account for the final step connecting the two frontiers.

5. 修改 word_set 防止重复访问 / Mutating word_set to prevent revisits

word_set -= next_front  # Remove explored words from the global set

如果不这样做，已经访问过的词可能从另一侧再次入队，导致死循环或错误结果。

6. beginWord 可能也在 wordList 中

题目不保证。用 word_set -= {beginWord} 防止重复访问自身。

Part 4: Real-World Application / 实际应用 (2 min)

中文： Word Ladder 的算法思想在生产系统中无处不在：

1. 拼写纠错 (Spell Correction)

Google/iOS 键盘的拼写建议：给定一个错误单词，找到编辑距离最近的正确单词。BFS 按编辑距离层次扩展，等价于 Word Ladder 的变体。

2. 知识图谱推理 (Knowledge Graph Reasoning)

3. 配置迁移 (Configuration Migration)

系统配置从版本 v1 迁移到 v5，每步只能应用一个合法的 migration 脚本，问最少几步？等价于图最短路径。

4. DNA 序列变异分析

生物信息学：从基因序列 A 到序列 B，每步只能改变一个碱基对（且中间序列必须是有意义的序列）。

English: Real production uses of this pattern:

• Autocorrect / fuzzy matching — find shortest edit distance to valid word; BFS on "word space" graph
• Knowledge graph shortest path — "6 degrees of separation" style queries in Neo4j / WikiData
• Network routing — each hop changes one attribute (VLAN, subnet) of a packet's path
• Code refactoring chains — automated refactoring where each intermediate state must compile

The bidirectional BFS pattern specifically appears in:

• LinkedIn's "degrees of connection" (bidi BFS between two users' connection graphs)
• Route planning (meet-in-the-middle optimization in GPS routing, e.g. A* bidirectional)
• Password cracking chains (rainbow tables = precomputed hash chain meet-in-the-middle)

Part 5: Interview Simulation / 面试模拟 (3 min)

Q1: 为什么用 BFS 而不是 DFS？Why BFS over DFS?

A: BFS guarantees shortest path in unweighted graphs by expanding layer by layer — the first time we reach a node, we've found the minimum distance. DFS might find a valid path but not the shortest one. Since the problem asks for minimum transformation length, BFS is the correct choice.

Q2: 你能优化你的初始 BFS 解法吗？Can you optimize your basic BFS?

A: Yes — bidirectional BFS. Instead of expanding from just one end, we simultaneously expand from both beginWord and endWord. We always expand the smaller frontier to keep both sides balanced. This reduces the search space from O(B^d) to O(B^(d/2)), an exponential improvement. In the worst case with branching factor 26 and depth 10, that's 26^10 vs 2×26^5 — roughly 11 billion nodes vs 22 million.

Q3: 双向 BFS 怎么知道两侧相遇了？How do you detect meeting in bidirectional BFS?

A: When expanding one frontier, check if any generated candidate appears in the OTHER frontier's set. If yes, the two sides have met — return steps + 1. Using sets (not queues) for frontiers enables O(1) lookup for this check.

Q4: 如果 beginWord 也需要在词典中怎么办？What if beginWord must also be in wordList?

A: The current LeetCode problem says beginWord doesn't need to be in wordList — it's the given start. If the constraint changed, we'd simply check if beginWord not in word_set: return 0 at the top, similar to the endWord check. The rest of the algorithm stays identical.

Q5: 这道题的 Follow-up：输出完整路径怎么做？Print the actual path?

A: That's LeetCode 126 (Word Ladder II — Hard). For a single shortest path, augment BFS to track parent pointers: parent[candidate] = word. After reaching endWord, backtrack from endWord to beginWord using the parent map. For ALL shortest paths (LC 126), we must be careful: allow multiple parents per node at the same BFS layer, and backtrack through all of them — this is significantly more complex and requires careful same-level handling.

总结 / Summary

时间复杂度 / Time: O(N × L × 26) where N = wordList size, L = word length

空间复杂度 / Space: O(N × L)