单词接龙 II

Category Difficulty Likes Dislikes
algorithms Hard (39.75%) 608 -
Tags

array | string | backtracking | breadth-first-search

Companies

amazon | yelp

按字典 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：

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"

示例 2：

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

提示：

  • 1 <= beginWord.length <= 5
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 500
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有单词 互不相同

广度优先搜索 + 回溯(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
/*
 * @lc app=leetcode.cn id=126 lang=cpp
 *
 * [126] 单词接龙 II
 */

// @lc code=start
class Solution {
public:

    void backtrack(vector<vector<string>> &res, const string &node, unordered_map<string, set<string>> &from, vector<string> path) {
        if (from[node].empty()) {
            res.push_back({path.rbegin(), path.rend()});
            return ;
        }
        for (const string &parent : from[node]) {
            path.push_back(parent);
            backtrack(res, parent, from, path);
            path.pop_back();
        }
    }

    /** 
     * if (str == endWord) res.push(str) return ;
     * if (current(str-1, str)) dp[0] = str - 1 dp[1] = str, else dp[0] = dp[1] = str - 1
     * 
     * hit -> hot ->c  
     * hit -> hit -> hit -> hit-> hit -> hit -> hit -> hit
     */
    vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {
        vector<vector<string>> res;
        unordered_set<string> dict = {wordList.begin(), wordList.end()};
        if (dict.find(endWord) == dict.end()) {
            return res;
        }

        /* beginWord在dict中是多余的 */
        dict.erase(beginWord);

        unordered_map<string, int> steps = {{beginWord, 0}};
        unordered_map<string, set<string>> from{{beginWord, {}}};
        int step = 0;
        bool found = false;
        queue<string> q = queue<string>{{beginWord}};
        int wordLen = beginWord.length();

        while (!q.empty()) {
            step++;
            int size = q.size();
            for (int i = 0; i < size; i++) {
                const string currWord = move(q.front());
                string nextWord = currWord;
                q.pop();
                for (int j = 0; j < wordLen; j++) {
                    const char origin = nextWord[j];
                    for (char c = 'a'; c <= 'z'; c++) {
                        nextWord[j] = c;
                        if (steps[nextWord] == step) {
                            from[nextWord].insert(currWord);
                        }
                        if (dict.find(nextWord) == dict.end()) {
                            continue;
                        }
                        dict.erase(nextWord);
                        q.push(nextWord);
                        from[nextWord].insert(currWord);
                        steps[nextWord] = step;
                        if (nextWord == endWord) {
                            found = true;
                        }
                    }
                    nextWord[j] = origin;
                }
            }
            if (found) {
                break;
            }
        }
        if (found) {
            vector<string> path = { endWord };
            backtrack(res, endWord, from, path);
        }
        return res;
    }
};
// @lc code=end