题目描述

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

• 每对相邻的单词之间仅有单个字母不同。
• 转换过程中的每个单词 s_i（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
• s_k == endWord

给你两个单词 beginWord 和 endWord，以及一个字典 wordList。请你找出并返回所有从 beginWord 到 endWord 的 最短转换序列，如果不存在这样的转换序列，返回一个空列表。每个序列都应该以单词列表 [beginWord, s_1, s_2, ..., s_k] 的形式返回。

样例

输入：
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"

输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释：endWord "cog" 不在字典 wordList 中，所以不存在符合要求的转换序列。

限制

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

算法

(宽度优先遍历，启发式搜索) $O(wordList.size() + |\Sigma|^{len})$

1. 此题可以转化为图论问题，可以转化的两个单词之间视为为一条边，且边权为 $1$。
2. 求出从终点单词开始到所有有点的单源最短路，并记录图中每个单词距离终点的距离 $d$，为了之后递归寻找所有最优路径时使用。
3. 记录下从起点到终点的最短距离 $minDis$，从起点开始递归启发式搜索寻找所有最短路径。对于当前节点 $u$，枚举其所有可以转化到的节点 $v$，如果当前步数加上 $v$ 到终点的最短距离恰好是起点到终点的最短路径，则说明这条边就是在最短路上的边，可以递归继续寻找 $v$ 的后继节点。

时间复杂度

• 节点数量为 $O(wordList.size())$，边数为 $O(|\Sigma|^{len})$，故总时间复杂度为 $O(wordList.size() + |\Sigma|^{len})$。

空间复杂度

• 需要 $O(wordList.size() + |\Sigma|^{len})$ 的额外空间存储宽搜的数据结构和答案数组。

C++ 代码

class Solution {
private:
    int len, min_dis;
    unordered_set<string> seen;

    unordered_map<string, int> d;

    string ed;
    vector<vector<string>> ans;
    vector<string> p;

    void bfs() {
        queue<string> q;
        q.push(ed);
        d[ed] = 0;

        while (!q.empty()) {
            string u = q.front();
            q.pop();

            for (int i = 0; i < len; i++) {
                string v = u;
                for (char ch = 'a'; ch <= 'z'; ch++) {
                    v[i] = ch;
                    if (seen.find(v) == seen.end())
                        continue;

                    if (d.find(v) == d.end()) {
                        d[v] = d[u] + 1;
                        q.push(v);
                    }
                }
            }
        }
    }

    void find_paths(const string &u) {
        p.push_back(u);

        if (u == ed) {
            ans.push_back(p);
            p.pop_back();

            return;
        }

        for (int i = 0; i < len; i++) {
            string v = u;
            for (char ch = 'a'; ch <= 'z'; ch++) {
                v[i] = ch;

                if (seen.find(v) == seen.end() || d.find(v) == d.end())
                    continue;

                if (p.size() + d[v] == min_dis)
                    find_paths(v);
            }
        }

        p.pop_back();
    }

public:
    vector<vector<string>> findLadders(string beginWord, string endWord,
        vector<string>& wordList
    ) {
        len = beginWord.size();
        seen = unordered_set<string>(wordList.begin(), wordList.end());

        if (seen.find(endWord) == seen.end())
            return {};

        seen.insert(beginWord);

        ed = endWord;
        bfs();

        min_dis = d[beginWord];
        find_paths(beginWord);

        return ans;
    }
};