LeetCode Word Ladder II：雙向 BFS 與路徑回溯

問題描述

給定起始詞、目標詞與字典，找出所有最短變換序列。每步僅改一字母，中間詞必須在字典中。

算法思路

1. BFS 建立前驅表：分層遍歷，用兩個 unordered_set 交替儲存當前層與下一層。刪除已訪問詞以防循環。記錄每個詞的前驅詞列表 precursor。
2. 遞歸回溯輸出路徑：從目標詞出發，沿前驅表 DFS 回溯至起始詞，反轉得到正向路徑。

優化要點

• 層次遍歷保證找到的均為最短路徑。
• 及時從字典移除已訪問詞，大幅剪枝。
• 使用 unordered_map> 儲存前驅關係。

核心代碼

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> findLadders(string start, string end, unordered_set<string> &dict) {
        dict.insert(start); dict.insert(end);
        unordered_map<string, vector<string>> precursor;
        for (auto &w : dict) precursor[w] = {};
        vector<unordered_set<string>> layers(2);
        layers[0].insert(start);
        int cur = 0, pre = 1;
        while (true) {
            swap(cur, pre);
            for (auto &w : layers[pre]) dict.erase(w);
            layers[cur].clear();
            for (auto &w : layers[pre]) {
                string str = w;
                for (int i = 0; i < str.size(); i++) {
                    char orig = str[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        str[i] = c;
                        if (dict.count(str)) {
                            precursor[str].push_back(w);
                            layers[cur].insert(str);
                        }
                    }
                    str[i] = orig;
                }
            }
            if (layers[cur].empty()) return res;
            if (layers[cur].count(end)) break;
        }
        vector<string> path;
        generatePath(precursor, path, end);
        return res;
    }
    void generatePath(auto &precursor, vector<string> &path, string end) {
        if (precursor[end].empty()) {
            path.push_back(end);
            auto tmp = path; reverse(tmp.begin(), tmp.end());
            res.push_back(tmp);
            path.pop_back(); return;
        }
        path.push_back(end);
        for (auto &pre : precursor[end]) generatePath(precursor, path, pre);
        path.pop_back();
    }
};