算法搜索

记录搜索路径；枚举点找边和枚举边找点

字数统计: 2.7k字   |   阅读时长: 12分
, ,

摘要:

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本文通过 126.单词接龙 II 主要介绍在搜索过程中如何记录搜索路径。因为有时候光搜到了还不行，还需要给出搜索到的具体路径。此外本题的枚举点找边改为枚举边找点也是一种经典的优化思路。

搜索过程记录路径的方法

DFS：开栈记录节点，在 dfs下一节点之前，先把当前节点压入；下一个节点的 dfs 回溯之后，栈顶是当前节点，先把它弹出。找到答案后，栈里记录的是路径。例如：113. 路径总和 II。

BFS：开一个 vector，bfs 到当前节点时，先记录其前驱或者前驱的列表。bfs 到目标点后，沿着前驱往回找可以得到路径(本题是以DFS的方式往回找)。

题目

126.单词接龙 II

给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。

说明:

1
2
3
4
5
如果不存在这样的转换序列，返回一个空列表。
所有单词具有相同的长度。
所有单词只由小写字母组成。
字典中不存在重复的单词。
你可以假设 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”]
输出: []
解释: endWord “cog” 不在字典中，所以不存在符合要求的转换序列。

题解

本题把路径寻找相关的点基本都涵盖了，值得反复推敲。

例如建图，双向搜索，染色，枚举边找点和枚举点着边等等。

算法: 双向BFS + DFS记录路径

在 127. 单词接龙 的基础上，在 BFS 过程中把每个访问到的节点的前驱记录下来。基础算法是双向BFS，思路和模板：双向搜索，【搜索难题】力扣127-双向BFS。

在BFS过程中，一个节点的前驱可能有多个，因此需要用邻接表记录。

获取到某个下一 level 的节点时，在记录前驱的邻接表中更新完之后，先不能把该点染成本方向(起点侧/终点侧)的颜色，因为之后可能还有点指向该点，这种情况将该点用一个新的颜色作为临时标记。本层所有节点访问完，并更新前驱邻接表之后，统一将所有临时标记的节点染色为当前方向。BFS过程中，节点有4中颜色，0: 为选过，1: 属于起点，2: 属于终点，3: 临时标记。

例如从起点 s=4 单向往终点 ed=3 BFS 时，第一次 bfs 得到 level1 的节点 0, 1, 2。level2 的节点只有 3，但是上一个 level 的 0, 1 均指向了该点，所以需要记录两条边。

在枚举当前层所有节点的后继时，如果发现有某个点被染成了反向的颜色，说明本次 BFS 结束之后已经找到最短的路径了。把染成反向颜色的点记录到哈希表里，称为关节，起到连接最终的路径的前半部分和后半部分的作用。

一层的 bfs 中，关节节点可能会同时发现好几个，这些关节对应的到起点到终点的距离都一样，只要有一个是最短路，则所有的都是最短路，因此找到第一个关节之后不能急着退出，需要把当前层所有节点的后继访问完，因为后面可能还有是关节。

例如下图例子，起点侧的第一层为 0、1，终点侧第一层为 4、5，正常更新。起点侧第二层为 2, 3 正常更新。但是在执行终点侧的第二层 BFS 时，发现后继 2, 3 已经被染成了反向的颜色，这两个点都是关节，将它们加到哈希表中。作为 DFS 找路径的起点。

现在有了两个前驱邻接表 prev1，prev2，两个邻接表的起点均为关节节点 ，终点分别为s, ed。枚举关节节点 joint，往 s 和 d 分别走一遍 dfs ，把关节到 s 和到 ed 的所有路径都记录下来，连接成完整路径记录进结果。

代码(C++)

两次搜索+双向搜索，实现起来很繁琐。

1135ms

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
class Solution {
public:
    vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int ed = -1, s = -1;
        int n = wordList.size();
        for(int i = 0; i < n; ++i)
        {
            if(wordList[i] == endWord)
                ed = i;
            if(wordList[i] == beginWord)
                s = i;
        }
        if(ed == -1) return vector<vector<string> >();
        if(s == -1)
        {
            wordList.push_back(beginWord);
            s = n;
            ++n;
        }
        vector<int> colors(n, 0); // 0: 未选; 1: 属于起点; 2: 属于终点; 3: 临时标记
        queue<int> q1, q2;
        q1.push(s);
        colors[s] = 1;
        q2.push(ed);
        colors[ed] = 2;
        vector<int> level_nodes; // 当前层的节点
        vector<vector<int> > prev1(n), prev2(n); // 分别记录起点侧和终点侧各个点的前驱列表
        unordered_set<int> joints; // 记录关节, 同一 level 的关节都要记进来
        while(!q1.empty() && !q2.empty())
        {
            // 更新起点侧的下一个 level 的节点
            bfs_step(q1, level_nodes, colors, 1, joints, prev1, wordList);
            if(!joints.empty()) break;
            // 更新终点侧的下一个 level 的节点
            bfs_step(q2, level_nodes, colors, 2, joints, prev2, wordList);
            if(!joints.empty()) break;
        }
        if(joints.empty()) return vector<vector<string> >();
        vector<vector<int> > prefixs, postfixs;
        vector<int> path;
        vector<vector<string> > result;
        vector<string> item;
        for(int joint: joints)
        {
            prefixs.clear();
            postfixs.clear();
            path.push_back(joint);
            dfs(prev1, joint, prefixs, path, s);
            dfs(prev2, joint, postfixs, path, ed);
            path.pop_back();
            for(vector<int> &prefix: prefixs)
                for(vector<int> &postfix: postfixs)
                {
                    item.clear();
                    for(int i = (int)prefix.size() - 1; i >= 1; --i)
                        item.push_back(wordList[prefix[i]]);
                    for(int i: postfix)
                        item.push_back(wordList[i]);
                    result.push_back(item);
                }
        }
        return result;
    }

private:
    void dfs(const vector<vector<int> >& prev, int cur, vector<vector<int> >& paths, vector<int>& path, int e)
    {
        if(cur == e)
        {
            paths.push_back(path);
            return;
        }

        for(int son: prev[cur])
        {
            path.push_back(son);
            dfs(prev, son, paths, path, e);
            path.pop_back();
        }
    }

    void bfs_step(queue<int>& q, vector<int>& level_nodes, vector<int>& colors, int color,
            unordered_set<int>& joints, vector<vector<int> >& prev, const vector<string>& wordList)
    {
        int n = colors.size();
        level_nodes.clear();
        while(!q.empty())
        {
            level_nodes.push_back(q.front());
            q.pop();
        }
        for(int node: level_nodes)
        {
            for(int i = 0; i < n; ++i)
            {
                if(i == node || colors[i] == color) continue;
                if(_check(wordList[i], wordList[node]))
                {
                    if(colors[i] == 0)
                        q.push(i);
                    if(colors[i] != 0 && colors[i] != 3)
                        joints.insert(i);
                    colors[i] = 3;
                    prev[i].push_back(node);
                }
            }
        }
        for(int i = 0; i < n; ++i)
            if(colors[i] == 3)
                colors[i] = color;
    }

    bool _check(const string& s1, const string& s2)
    {
        int cnt = 0;
        for(int i = 0; i < (int)s1.size(); ++i)
            if(s1[i] != s2[i])
                ++cnt;
        return cnt == 1;
    }
};

优化: 枚举点找边改成枚举边找点

获取相邻单词是遍历 wordList 逐一比对完成的，获取一个单词的所有相邻单词的时间复杂度为 O(NL)。这个可以理解为枚举点找边：先枚举存在的点(单词)，看它与当前词构成一条边(只相差一个字母)。

也可以用枚举边找点的思路：枚举单词的所有位置 0 <= i <= L-1，在枚举所有的小写字母 c，当前词的 i 位置改为 c 形成一个新单词(可以理解为枚举了一条边)，然后看新单词(点)是否在单词表中，若存在，则在记录前驱的邻接表中更新新单词的边。查找单词是否在单词表存在的操作需要开哈希表，键是词典中的词，值是对应的节点的编号。时间复杂度O(26*L)。这与 O(NL) 相比是很大的优化。此优化也可以用到 127 题中。

总时间复杂度从 $O(N^{2}L)$ 优化成了 $O(26NL)$

代码 (C++)

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class Solution {
public:
    vector<vector<string> > findLadders(string beginWord, string endWord, vector<string>& wordList) {
        int ed = -1, s = -1;
        int n = wordList.size();
        unordered_map<string, int> mapping;
        for(int i = 0; i < n; ++i)
        {
            if(wordList[i] == endWord)
                ed = i;
            if(wordList[i] == beginWord)
                s = i;
            mapping[wordList[i]] = i;
        }
        if(ed == -1) return vector<vector<string> >();
        if(s == -1)
        {
            wordList.push_back(beginWord);
            s = n;
            mapping[beginWord] = s;
            ++n;
        }
        vector<int> colors(n, 0); // 0: 未选; 1: 属于起点; 2: 属于终点; 3: 临时标记
        queue<int> q1, q2;
        q1.push(s);
        colors[s] = 1;
        q2.push(ed);
        colors[ed] = 2;
        vector<int> level_nodes; // 当前层的节点
        vector<vector<int> > prev1(n), prev2(n); // 分别记录起点侧和终点侧各个点的前驱列表
        unordered_set<int> joints; // 记录关节, 同一 level 的关节都要记进来
        while(!q1.empty() && !q2.empty())
        {
            // 更新起点侧的下一个 level 的节点
            bfs_step(q1, level_nodes, colors, 1, joints, prev1, wordList, mapping);
            if(!joints.empty()) break;
            // 更新终点侧的下一个 level 的节点
            bfs_step(q2, level_nodes, colors, 2, joints, prev2, wordList, mapping);
            if(!joints.empty()) break;
        }
        if(joints.empty()) return vector<vector<string> >();
        vector<vector<int> > prefixs, postfixs;
        vector<int> path;
        vector<vector<string> > result;
        vector<string> item;
        for(int joint: joints)
        {
            prefixs.clear();
            postfixs.clear();
            path.push_back(joint);
            dfs(prev1, joint, prefixs, path, s);
            dfs(prev2, joint, postfixs, path, ed);
            path.pop_back();
            for(vector<int> &prefix: prefixs)
                for(vector<int> &postfix: postfixs)
                {
                    item.clear();
                    for(int i = (int)prefix.size() - 1; i >= 1; --i)
                        item.push_back(wordList[prefix[i]]);
                    for(int i: postfix)
                        item.push_back(wordList[i]);
                    result.push_back(item);
                }
        }
        return result;
    }

private:
    void dfs(const vector<vector<int> >& prev, int cur, vector<vector<int> >& paths, vector<int>& path, int e)
    {
        if(cur == e)
        {
            paths.push_back(path);
            return;
        }

        for(int son: prev[cur])
        {
            path.push_back(son);
            dfs(prev, son, paths, path, e);
            path.pop_back();
        }
    }

    void bfs_step(queue<int>& q, vector<int>& level_nodes, vector<int>& colors, int color,
            unordered_set<int>& joints, vector<vector<int> >& prev, const vector<string>& wordList, const unordered_map<string, int>& mapping)
    {
        int L = wordList[0].size();
        int n = colors.size();
        level_nodes.clear();
        while(!q.empty())
        {
            level_nodes.push_back(q.front());
            q.pop();
        }
        for(int node: level_nodes)
        {
            string nxt = wordList[node];
            for(int pos = 0; pos < L; ++pos)
            {
                for(char c = 'a'; c <= 'z'; ++c)
                {
                    if(wordList[node][pos] == c) continue;
                    nxt[pos] = c;
                    auto it = mapping.find(nxt);
                    if(it != mapping.end())
                    {
                        int i = it -> second;
                        if(colors[i] != color)
                        {
                            if(colors[i] == 0)
                                q.push(i);
                            if(colors[i] != 0 && colors[i] != 3)
                                joints.insert(i);
                            colors[i] = 3;
                            prev[i].push_back(node);
                        }
                    }
                    nxt[pos] = wordList[node][pos];
                }
            }
        }
        for(int i = 0; i < n; ++i)
            if(colors[i] == 3)
                colors[i] = color;
    }
};
Share