力扣（LeetCode）126. 单词接龙 II（2022.05.06）

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> … -> sk 这样的单词序列，并满足：

每对相邻的单词之间仅有单个字母不同。
转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
sk == endWord
给你两个单词 beginWord 和 endWord ，以及一个字典 wordList 。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列 ，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s1, s2, …, sk] 的形式返回。

示例 1：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出：[[“hit”,“hot”,“dot”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
解释：存在 2 种最短的转换序列：
“hit” -> “hot” -> “dot” -> “dog” -> “cog”
“hit” -> “hot” -> “lot” -> “log” -> “cog”
示例 2：

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,“dot”,“dog”,“lot”,“log”]
输出：[]
解释：endWord “cog” 不在字典 wordList 中，所以不存在符合要求的转换序列。

提示：

1 <= beginWord.length <= 5
endWord.length == beginWord.length
1 <= wordList.length <= 5000
wordList[i].length == beginWord.length
beginWord、endWord 和 wordList[i] 由小写英文字母组成
beginWord != endWord
wordList 中的所有单词 互不相同

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/word-ladder-ii

方法一：双向BFS

C++提交内容：

class Solution {
public:
    vector> findLadders(string beginWord, string endWord, vector& wordList) {
        vector> res;
        unordered_set dict(wordList.begin(), wordList.end()), head{beginWord}, tail{endWord};
        if(!dict.count(endWord)) return res;
        dict.erase(beginWord), dict.erase(endWord);
        unordered_map> next;
        bool reversed = false, found = false; // 一些初始化准备
        while (!head.empty()) {
            unordered_set temp; // 保存已转化过的 string
            for (const auto &w : head) { // 层 遍历
                string s = w;
                for (size_t i = 0; i < s.size(); ++i) { // 回溯查找子节点
                    char c = s[i];
                    for (char j = 'a'; j <= 'z'; ++j) {
                        s[i] = j;
                        if (tail.count(s)) { // 退出条件
                            reversed ? next[s].push_back(w) : next[w].push_back(s);
                            found = true;
                        }
                        if (dict.count(s)) { // 保存已转换的子节点
                            reversed ? next[s].push_back(w) : next[w].push_back(s);
                            temp.insert(s);
                        }
                    }
                    s[i] = c;
                }
            }
            if (found) break; // 退出
            for (const auto &w : temp) dict.erase(w); // 删除已转换的 string
            if (temp.size() <= tail.size()) head = temp; // 根据左右层节点大小来切换遍历方向
            else {
                reversed = !reversed;
                head = tail;
                tail = temp;
            }
        }
        if (found) { // 根据上面双向BFS构建的树型数据结构来梳理出不同的转换序
            vector path = {beginWord};
            backtracking(beginWord, endWord, next, path, res); // 回溯算法的应用
        }
        return res;
    }

private:
    void backtracking(const string &src, const string &dst, unordered_map> &next,
        vector &path, vector> &res) {
        if (src == dst) res.push_back(path);
        for (const auto &w : next[src]) { // 按 层 为单位回溯求不同的转换序
            path.push_back(w);
            backtracking(w, dst, next, path, res);
            path.pop_back();
        }
    }
};