leetcode-126.单词接龙 II

深度优先搜索(dfs)

广度优先搜索(bfs)

回溯法

---

题目详情

按字典 wordList 完成从单词 beginWord 到单词 endWord 转化，一个表示此过程的 转换序列 是形式上像 beginWord -> s1 -> s2 -> ... -> sk 这样的单词序列，并满足：
1.每对相邻的单词之间仅有单个字母不同。
2.转换过程中的每个单词 si（1 <= i <= k）必须是字典 wordList 中的单词。注意，beginWord 不必是字典 wordList 中的单词。
3.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"
1
2
3
4
5

示例2:

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

我的代码：

总结自LeetCode101

我们可以把起始字符串、终止字符串、以及单词表里所有的字符串想象成节点。若两个字符串只有一个字符不同，那么它们相连。因为题目需要输出修改次数最少的所有修改方式，因此我们可以使用广度优先搜索，求得起始节点到终止节点的最短距离。
我们同时还使用了一个小技巧：我们并不是直接从起始节点进行广度优先搜索，直到找到终止节点为止；而是从起始节点和终止节点分别进行广度优先搜索，每次只延展当前层节点数最少的那一端，这样我们可以减少搜索的总结点数。举例来说，假设最短距离为 4，如果我们只从一端搜索 4 层，总遍历节点数最多是 1 + 2 + 4 + 8 + 16 = 31；而如果我们从两端各搜索两层，总遍历节点数最多只有 2 × (1 + 2 + 4) = 14。
在搜索结束后，我们还需要通过回溯法来重建所有可能的路径。

class Solution 
{
public:
    //                    beginword          endword                  
    void backtracking(const string &src, const string &dst, unordered_map<string,vector<string>> &next, vector<string> &path,vector<vector<string>> &ans)
    {
       if (src == dst)          //最终单词相同后,将path(路径)计入ans,递归出口
       {
           ans.push_back(path);
           return;
       }     
       for (const auto &s: next[src])   //从前往后的next[src]中的每一个单词
       {
           path.push_back(s);               //依次存入path
           backtracking(s, dst, next, path, ans);   //递归来全部存入
           path.pop_back();                 //这里将path中的元素回溯清空(能回溯path肯定完整,已经存入ans了)
       }
    }
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) 
    {
        vector<vector<string>> ans;
        unordered_set<string> dict;     
        for (const auto &w: wordList)   //将wordList单词全部存入dict,从而后面操作dict不影响wordList
        {
            dict.insert(w);
        }
        if (!dict.count(endWord))       //如果需要寻找的endWord不在wordList中,按题目要求要返回空列表
        {
            return ans;
        }
        //从dict中删去起点和终点
        dict.erase(beginWord);          
        dict.erase(endWord);
        //q1,q2用来分别记录头尾起点的路径
        unordered_set<string> q1{beginWord}, q2{endWord};
        //                             即下面的链next[w]                     链next[s]
        //next的功能是存储两个path,一个是从beginWord->...->endWord,另一个是endWord->...->beginWord
        //这个正是运用到的一个小技巧,双头分别寻找来提高效率
        unordered_map<string, vector<string>> next; 
        //reversed记录是否反过来寻找过,即是否变成从尾部往前走了
        bool reversed = false, found = false;
        while (!q1.empty())
        {
            unordered_set<string> q;
            for (const auto &w: q1)
            {
                string s = w;
                //遍历q1单词每一个字母,并依次尝试改变某个字母(利用ch暂存改变前的字母以便恢复)
                for (size_t i = 0; i < s.size(); ++i)   
                {
                    char ch = s[i];     //暂存遍历到的这个字母
                    //这个单词的每个位置的每个改变都尝试一次
                    for (int j = 0; j < 26; ++j)
                    {
                        s[i] = j + 'a';         //0-25 + 'a' 表示的就是'a'-'z'
                        if (q2.count(s))        //如果本次尝试改变后s和q2即endWord那头相同了(即达到目的)(qwq接到头了)
                        {
                            //如果反转过则将w(从前往后的)插入链next[s]中,否则将s(从后往前的)插入next[w]中 下同
                            //        s(改变后的)->w(改变前)   w->s(这个是答案需要的顺序)
                            //因为这里reversed了,所以路径是反的,所以要用s->w来正向过来
                            reversed? next[s].push_back(w): next[w].push_back(s);
                            found = true;       //found置true
                        }
                        if (dict.count(s))      //如果没达到目的 且 目标单词s还存在于dict即单词表中
                        {
                            reversed? next[s].push_back(w): next[w].push_back(s);
                            q.insert(s);    //现在s还没有恢复原来的,但是s在dict中,说明可以从此处连接一条path
                                            //将s存入q中(q的作用看下面)
                        }
                    }
                    s[i] = ch;      //恢复s
                }
            }
            if (found)      //找到则跳出while
            {
                break;
            }
            //这里q的作用:从dict中删除我们已经计入path的单词,防止重复
            for (const auto &w: q)  
            {
                dict.erase(w);
            }
            //q1存的是短的那头
            //如果q <= q2,说明正在操作的这个方向(首尾都有可能)是短的path,将较短q1赋为q
            if (q.size() <= q2.size())
            {
                q1 = q;
            }
            else //如果q.size() > q2.size() 则说明q2那头短,需要reversed,从而下次优先操作短的
            //reversed作用很大,上面只有用reversed才能知道是next[s]还是next[w]而不必管q1,q2
            {
                reversed = !reversed;
                q1 = q2;    //短头给q1
                q2 = q;     //长头给q2暂存,后面也有可能一比较他又短了
            }
        }
        if (found)  //最后如果found,说明next中已经存好了路径,需要通过递归来提取到ans中
        {
            vector<string> path = {beginWord};
            backtracking(beginWord, endWord, next, path, ans);
        }
        return ans;
    }
};
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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

涉及知识点:

1.深度优先搜索(dfs)

深度优先搜索（depth-first seach，DFS）在搜索到一个新的节点时，立即对该新节点进行遍历；因此遍历需要用先入后出的栈来实现，也可以通过与栈等价的递归来实现。对于树结构而言，由于总是对新节点调用遍历，因此看起来是向着“深”的方向前进。

2.广度优先搜索(bfs)

广度优先搜索（breadth-first search，BFS）不同与深度优先搜索，它是一层层进行遍历的，因此需要用先入先出的队列而非先入后出的栈进行遍历。由于是按层次进行遍历，广度优先搜索时按照“广”的方向进行遍历的，也常常用来处理最短路径等问题。

3.回溯法

回溯法（backtracking）是优先搜索的一种特殊情况，又称为试探法，常用于需要记录节点状
态的深度优先搜索。通常来说，排列、组合、选择类问题使用回溯法比较方便。
顾名思义，回溯法的核心是回溯。在搜索到某一节点的时候，如果我们发现目前的节点（及
其子节点）并不是需求目标时，我们回退到原来的节点继续搜索，并且把在目前节点修改的状态
还原。这样的好处是我们可以始终只对图的总状态进行修改，而非每次遍历时新建一个图来储存
状态。在具体的写法上，它与普通的深度优先搜索一样，都有 [修改当前节点状态]→[递归子节
点] 的步骤，只是多了回溯的步骤，变成了 [修改当前节点状态]→[递归子节点]→[回改当前节点
状态]。