LeetCode 筆記：Word Ladder（單詞接龍）BFS 最短路徑詳解

題目大意

給定起始單詞、目標單詞和字典，每次只能改變一個字母，且中間單詞必須在字典中。求從 start 到 end 的最短轉換序列長度。例如 hit → hot → dot → dog → cog 長度為 5。

圖模型與 BFS

將每個單詞視為圖的頂點，差一個字母的單詞連邊。字符集為小寫字母，長度固定 L，每個單詞最多有 25×L 條潛在邊。檢查這些變體是否在字典中即可構建圖。求最短路徑用廣度優先搜索（BFS）。

關鍵優化：刪除已訪單詞

BFS 遍歷時，將已入隊的單詞從字典中刪除。因為 BFS 層序遍歷保證首次到達即為最短路徑，刪除不影響最優性，且能防止死循環（如 hog → hot → hog）。

層次分隔技巧

隊列中用空字符串 "" 標記層結束。每遇到層分隔符且隊列非空，深度加一並重新入隊分隔符。

參考實現

int ladderLength(string start, string end, unordered_set<string> &dict) {
    if (start.empty() || end.empty()) return 0;
    queue<string> q;
    q.push(start); q.push(""); // 層分隔
    int path = 1;
    while (!q.empty()) {
        string str = q.front(); q.pop();
        if (str != "") {
            for (int i = 0; i < str.size(); ++i) {
                char tmp = str[i];
                for (char c = 'a'; c <= 'z'; ++c) {
                    if (c == tmp) continue;
                    str[i] = c;
                    if (str == end) return path + 1;
                    if (dict.count(str)) {
                        q.push(str);
                        dict.erase(str); // 關鍵：刪除防重
                    }
                }
                str[i] = tmp;
            }
        } else if (!q.empty()) {
            ++path;
            q.push("");
        }
    }
    return 0;
}

總結

BFS 配合字典刪除策略，時間複雜度 O(N·L·26)，空間 O(N)，是解決單詞接龍的標準方法。