leetcode126.单词接龙Ⅱ

Posted on | In |
Words count in article: 707 | Reading time ≈ 3

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

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

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

示例：

1
2
3
4
5
输入：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
由于题目要求没对相邻单词之间仅有单个字母不同，即从当前状态到下一个状态代价为1，同时题目要求最短转化路近，因此问题转化为BFS求最短路问题

1、首先，利用BFS逆向求出每个单词到endWord的单源最短路径
2、在利用DFS求最短路径，某个单词在要最短路上，距离一定等于最小距离

代码

  • 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
class Solution {
public:
    int len, min_dis;
    unordered_set<string> seen; // 合理的单词
    unordered_map<string, int> d; //距离
    string ed;
    vector<vector<string>> res; // 所有路径
    vector<string> p; // 单个路径

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

        while (!q.empty()) {
            auto 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 dfs(const string& u) {
        p.push_back(u);
        if (u == ed) {
            res.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)
                    dfs(v);
            }
        }
        p.pop_back(); // 回溯
    }

    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];
        dfs(beginWord);

        return res;
    }
};

[原题链接](126. 单词接龙 II - 力扣（Leetcode）)

[相似题目](127. 单词接龙 - 力扣（Leetcode）)

0%