题目描述

给定两个单词 (beginWord和endWord)以及一个单词列表，请找出所有从beginWord到endWord的最短转化序列。
转化序列需要满足：

1. 每次只能改变一个字母；
2. 转化过程中的单词，必须出现在单词列表中（除了beginWord之外）；

注意：

• 如果不存在任何转化方案，请返回空数组；
• 数据中所有单词的长度均相等；
• 所有单词仅包含小写英文字母；
• beginWord和endWord均非空，且不相等；

样例1

输入：

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

输出：

[
  ["hit","hot","dot","dog","cog"],
  ["hit","hot","lot","log","cog"]
]

样例2

输入：

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

输出：

Output: []

解释：由于cog不在单词列表中，所以不存在任何转化方案。

算法

(BFS+DFS) $O(2^nnL)$

这道题目比较复杂，我们一步一步来解决。

首先考虑如何建图，有两种方式：

• 枚举所有单词对，然后判断是否可以通过改变一个字母相互转化，时间复杂度 $O(n^2L)$；
• 枚举每个单词，然后枚举该单词的每一位字母，再枚举这一位的所有备选字母，然后再判断改变后的字符串是否存在，时间复杂度 $O(26nL^2)$。

我们要根据数据范围选择使用哪种建图方式，如果 $26L > n$，则用第二种，否则用第一种。经测试，早先leetcode上两种方式都是可以AC的，但后来增加了 $n$ 的大小，但并未增加 $L$ 的大小，所以第二种建图方式会超时，于是我们选择第一种建图方式即可。

然后，计算所有点 $i$ 到起点 $S$ 的最短距离 $dist[i]$。由于边权都是1，所以用BFS即可。

最后，我们利用 $dist[]$ 数组爆搜出所有最短路径：
从终点 $T$ 开始搜索，首先枚举终点的所有邻接点 $v$，如果 $dist[v] + 1 == dist[T]$，则说明存在一条最短路径，最后一步是从 $v$ 走到 $T$；然后递归搜索节点 $v$，依此类推，直到搜索到起点 $S$ 为止，说明找到了一条从 $S$ 到 $T$ 的最短路径。

时间复杂度分析：

1. 建图，通过上述分析可知，时间复杂度是 $O(26nL^2)$；
2. 求最短路用的是BFS，每个节点仅会遍历一次，每个点遍历时需要$O(L)$的计算量，所以时间复杂度是 $O(nL)$；
3. 求方案用的是DFS，总方案数是指数级的，再加上记录方案需要 $O(nL)$ 的时间，所以时间复杂度是 $O(2^nnL)$；

所以总时间复杂度是 $O(26nL^2 + nL + 2^nnL)$ = $O(2^nnL)$。

C++ 代码

class Solution {
public:
    vector<vector<string>> ans;
    vector<string> path;
    unordered_set<string> S;
    unordered_map<string, int> dist;

    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        for (auto& word: wordList) S.insert(word);
        queue<string> q;
        q.push(beginWord);
        dist[beginWord] = 0;
        while (q.size()) {
            auto t = q.front();
            q.pop();
            string r = t;
            for (int i = 0; i < t.size(); i ++ ) {
                t = r;
                for (char j = 'a'; j <= 'z'; j ++ )
                    if (j != r[i]) {
                        t[i] = j;
                        if (S.count(t) && dist.count(t) == 0) {
                            dist[t] = dist[r] + 1;
                            if (t == endWord) break;
                            q.push(t);
                        }
                    }
            }
        }

        if (dist.count(endWord)) {
            path.push_back(beginWord);
            dfs(beginWord, endWord);
        }

        return ans;
    }

    void dfs(string st, string ed) {
        if (st == ed) {
            ans.push_back(path);
            return;
        }

        string r = st;
        for (int i = 0; i < st.size(); i ++ ) {
            st = r;
            for (char j = 'a'; j <= 'z'; j ++ )
                if (j != r[i]) {
                    st[i] = j;
                    if (S.count(st) && dist[r] + 1 == dist[st]) {
                        path.push_back(st);
                        dfs(st, ed);
                        path.pop_back();
                    }
                }
        }
    }
};