LeetCode 127 單詞接龍：BFS 最短路徑 + 鄰接節點動態生成優化

題目重述

給定起始單詞 beginWord、目標單詞 endWord、字典 wordList。每步只能改變一個字母，且中間單詞必須在字典中。求從 beginWord 到 endWord 的最短轉換序列長度（含首尾）。無法轉換返回 0。

例：hit → hot → dot → dog → cog，長度 5。

建模：無權圖單源最短路徑

• 節點：所有單詞（含 begin/end）。
• 邊：兩單詞僅差一個字母 ⇔ 可相互轉換。
• 目標：BFS 求無權圖最短路徑長度。

方法一：預構建鄰接矩陣（超時）

// 構建 word -> id 映射
// 雙重循環 O(V^2 * L) 檢查每對單詞是否相鄰
// BFS 在鄰接矩陣上跑

缺陷：$V \le 5000$，$V^2 = 2.5 \times 10^7$，配合字符串比較 $O(L)$ 導致預處理極慢，記憶體 $O(V^2)$ 過大。

方法二：BFS 過程中動態生成鄰接節點（AC）

核心洞見：不必預先構建圖。訪問到單詞 cur 時，枚舉其每個位置換成 'a'..'z'，查詢新單詞是否在字典中（$O(1)$ 哈希查找）。

優化關鍵

1. 用 unordered_set 存字典：查找 $O(1)$ 期望，避免 $O(V)$ 線性掃描。
2. 就地修改字符串：避免構建大量臨時字符串對象。
3. 雙向 BFS 可進一步優化（本題單向已足夠）。

完整代碼

class Solution {
public:
    int ladderLength(string beginWord, string endWord, unordered_set& wordList) {
        if (wordList.find(endWord) == wordList.end()) return 0;
        
        queue q;
        unordered_set visited;
        q.push(beginWord);
        visited.insert(beginWord);
        int level = 1;
        
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                string cur = q.front(); q.pop();
                if (cur == endWord) return level;
                
                string next = cur;
                for (int i = 0; i < cur.size(); ++i) {
                    char orig = next[i];
                    for (char c = 'a'; c <= 'z'; ++c) {
                        if (c == orig) continue;
                        next[i] = c;
                        if (wordList.count(next) && !visited.count(next)) {
                            visited.insert(next);
                            q.push(next);
                        }
                    }
                    next[i] = orig; // 恢復
                }
            }
            ++level;
        }
        return 0;
    }
};

複雜度分析

• 時間：$O(V \cdot L \cdot 26)$。每個單詞出隊一次，枚舉 $L$ 位置 × 26 字母，哈希查找 $O(1)$。$V \le 5000, L \le 10$ → 約 $1.3 \times 10^6$ 操作，極快。
• 空間：$O(V \cdot L)$ 存儲字典與訪問集合。

進階優化：雙向 BFS

從 beginWord 和 endWord 同時擴展，每次擴展較小的前沿，相遇時返回。時間複雜度約降為 $O(b^{d/2})$（$b$ 分支因子，$d$ 深度），對大字典顯著加速。

// 雙向 BFS 骨架
unordered_set beginSet{beginWord}, endSet{endWord}, visited;
int level = 1;
while (!beginSet.empty() && !endSet.empty()) {
    if (beginSet.size() > endSet.size()) swap(beginSet, endSet);
    unordered_set nextSet;
    for (auto& w : beginSet) {
        string nxt = w;
        for (int i=0;i