题目链接：126. 单词接龙 II

题解：

是一道难题，DFS和BFS的结合使用！

题目简述：

给定两个不一样的单词和一个字典，找到所有从一个单词到另一个单词的序列！

单词的变化每次转换只能改变一个字母，字典中不一定存在起始单词！

题解：

这道题本质是一道求最短路的问题：即从起始单词到结束单词的最短路，并且边权为一，可以使用BFS来求最短路！

这道题不仅仅要求最短路的长度，而是要记录出所有最短路的路径，这里需要使用DFS来搜索路径！

关于建图方法： 假设单词数为n，单词长度为L

  • 枚举所有单词，判断两两单词（n^2）是否只有一位不同（L），为 n^2L
  • 枚举每个单词，每个单词的每一位（26nL）判断是否只有一位不同，哈希表优化判断存在或使用过，为 26nL^2

简单计算： 当26L < n 时，使用第二种，否则使用第一种，本题的数据为n > 26L，所以要使用第二种，否则超时

进入正题！！！本题思路：

DFS + BFS：

  • 使用BFS来求一个dist数组，表示当前点到起始点的最短路径长度
    • 使用第二种建图方式，即要枚举每一位的二十六种变化即可，若该点在字典中并且没有被遍历过，即S.count(t) && dist.count(t) == 0，我们就进行遍历dist[t] = dist[s] + 1，正常宽搜顺序，将当前点加入队列即可！
    • 若搜到了终点，直接break，跳到上一层循环，防止搜索不必要的路径
  • 通过dist数组来倒着DFS搜索到起点的路径即可 dfs(endWord)
    • 对于最当前点s，只需要搜索可以到达改点的路径，即s的邻接点，并且只要保证dist[s] = dist[t] + 1即说明有一条从t到s的最短路径，当然我们要保证该点在字典中即dist.count(t) != 0
    • 接下来继续向上搜索，直到起始单词，由于路径数组path是倒序存储的，所以搜到起点要将容器进行反转计入答案，完事之后再将其恢复
  • 若BFS搜完发现最短路径数组dist中没有终点单词，即dist.count(endWord) == 0，说明字典中都没有终点单词或者通过字典中单词根本变不成终点单词，直接return，防止进行不必要的DFS

注意：

  • 对于BFS的生成的单词是否在字典中的判断，采用了unordered_set来做，提前将其全部插入哈希表，判断为O(L)
  • 对于DFS的生成的单词是否在字典中的判断，采用dist数组来做，为什么不采用BFS用到的S数组呢？因为字典中不一定有起始单词，而dist一定有

时间复杂度：

  1. 建图：见上面建图分析，为O(26nL^2)
  2. 最短路BFS：每个点遍历一次，每次需要O(L)进行判断字典中是否存在或使用过，总共为O(nL)
  3. 搜索路径DFS：路径数量是指数级别的，记录方案需要O(nL)，总共为O(2^n nL)

终上为：O(26nL^2 + nL + 2^n nL) = O(2^n nL)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    vector<vector<string>> res;
    vector<string> path;
    unordered_set<string> S;
    unordered_map<string, int> dist;
    string beginWord;
    queue<string> q;
    vector<vector<string>> findLadders(string _beginWord, string endWord, vector<string>& wordList) {
        beginWord = _beginWord;
        q.push(beginWord);
        dist[beginWord] = 0;
        for(auto x : wordList) S.insert(x); 
        while(q.size()){
            auto s = q.front();
            q.pop();
            for(int i = 0; i < s.size(); i++){
                string t = s;
                for(char j = 'a'; j <= 'z'; j++){
                    if(j == t[i]) continue;
                    t[i] = j;
                    if(S.count(t) && dist.count(t) == 0){
                        dist[t] = dist[s] + 1;
                        if(t == endWord) break;
                        q.push(t);
                    }
                }
            }
        }
        if(dist.count(endWord) == 0) return res;
        path.push_back(endWord);
        dfs(endWord);
        return res;
    }
    void dfs(string s){
        if(s == beginWord){
            reverse(path.begin(), path.end());
            res.push_back(path);
            reverse(path.begin(), path.end());
            return;
        }
        for(int i = 0; i < s.size(); i++){
            string t = s;
            for(char j = 'a'; j <= 'z'; j++){
                if(j == s[i]) continue;
                t[i] = j;
                if(dist.count(t) && dist[t] + 1 == dist[s]){
                    path.push_back(t);
                    dfs(t);
                    path.pop_back();
                }
            }
        }
    }
};