LeetCode Word Ladder：單詞接龍最短路徑的 BFS 解法

題目描述

給定起始單詞 start、目標單詞 end 及字典 dict，每次僅能改變一個字母，且中間單詞必須在字典中。求從 start 到 end 的最短轉換序列長度。若無法轉換返回 0。

範例：start="hit", end="cog", dict=["hot","dot","dog","lot","log"] → 最短路徑 hit→hot→dot→dog→cog，長度 5。

BFS 解題思路

將每個單詞視為圖中的節點，邊連接僅差一字母的單詞。BFS 從 start 層層擴展，首次到達 end 即為最短路徑。隊列中存儲 (word, level) 對，level 表示當前步數。

1. 將 start 入隊，層級為 1。
2. 彈出隊首，對其每個位置嘗試替換為 'a'~'z'，生成新單詞。
3. 若新單詞等於 end，返回 level+1。
4. 若新單詞在字典中，入隊並從字典移除（避免重複訪問）。
5. 隊列為空仍未找到則返回 0。

C++ 實現

class Solution {
public:
    int ladderLength(string start, string end, unordered_set &dict) {
        queue> q;
        if (start.empty() || end.empty()) return 0;
        int len = start.size();
        if (start == end) return 1;
        q.push({start, 1});
        while (!q.empty()) {
            auto [word, lvl] = q.front(); q.pop();
            for (int i = 0; i < len; ++i) {
                char orig = word[i];
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c == orig) continue;
                    word[i] = c;
                    if (word == end) return lvl + 1;
                    if (dict.count(word)) {
                        q.push({word, lvl + 1});
                        dict.erase(word);
                    }
                }
                word[i] = orig;
            }
        }
        return 0;
    }
};

複雜度分析

• 時間：O(N × L × 26)，N 為字典大小，L 為單詞長度。
• 空間：O(N) 存儲字典與隊列。

優化方向：雙向 BFS 可進一步降低搜索空間。