Keshawn_lu's Blog

Leetcode 126. 单词接龙 II

字数统计: 1.3k阅读时长: 5 min
2020/06/07 Share

题目简介:

给定两个单词(beginWordendWord)和一个字典 wordList,找出所有从 beginWordendWord 的最短转换序列。转换需遵循如下规则:

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

说明:

  • 如果不存在这样的转换序列,返回一个空列表。
  • 所有单词具有相同的长度。
  • 所有单词只由小写字母组成。
  • 字典中不存在重复的单词。
  • 你可以假设 beginWordendWord 是非空的,且二者不相同。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]

输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]

示例 2:

1
2
3
4
5
6
7
8
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]

输出: []

解释: endWord "cog" 不在字典中,所以不存在符合要求的转换序列。

思路:

讲真这题是真的难…看着官方题解懂了七七八八,但是还没吃透。

为了方便将每个单词设置一个id,设置了word -> idid -> word的两个映射,方便后续的操作。

先将单词表中的单词加入这两个映射,若单词表中不存在结束单词,则说明无法通过转换达到,返回空即可。

然后开始构图,将每个单词看作一个结点,若两个单词不同字母数为1(题目给定单词均为相等长度,不用考虑长度的问题),说明能互相转换,则在这两个结点之间添加两条有向边。

接下来设置一个队列开始广度优先搜索,队列中的每一个元素都是从起点开始,到某一个结点结束的路径。

将从队列拿出的当前元素记为now_path,若它的最后一个元素,即此路径的结束结点和我们所需要的结束单词相同,则此路径为答案路径之一,存入res中。

若不同,则依次循环此结束结点所连接的下一个结点,记为next。设置一个cost数组,cost[id]代表从起始单词出发,到id代表的单词时,需要转换的最少次数

若刚才路径上的最后一个单词记为last_word,那么若cost[last_word] + 1 <= cost[next],(相等也可以的目的是找到相同长度的路径),则将next结点加入路径中,并压入队列。否则,便说明当前路径并不为最短路径(之前已经有更短的路径访问过这个结点)。这也说明了在队列中拿出的路径元素,若最后一个单词与目标结束单词相等,则此路径便为最短路径

最后返回res即可。

tips:

  • bool check_transform(string &word1, string &word2)函数中,若参数不加&,便会超时,原因是因为C++不加&,是函数参数值传递,需要重新拷贝一份数据,所以慢。而加&是引用传递,用的还是原来在内存的变量,不需要花时间拷贝一份。
  • cost[last_word] + 1 <= cost[next]相当于 cost[last_word] + 1 == cost[next] || cost[next] == INT_MAX
  • 对BFS有了初步的了解…

代码如下:

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
class Solution {
public:

//判断两个单词能否互相转换
bool check_transform(string &word1, string &word2){

int difference = 0;
for(int i = 0; i < word1.length() && difference < 2; i++){

if(word1[i] != word2[i])
difference++;
}

return difference == 1;
}

vector<vector<string>> findLadders(string beginWord, string endWord, vector<string>& wordList) {

unordered_map<string, int> wordId; //word->ID的映射
vector<string> idWord; //ID->word的映射
vector<vector<int>> edges; //构造图

int id = 0;
for(int i = 0; i < wordList.size(); i++){

if(!wordId.count(wordList[i])){

wordId[wordList[i]] = id++;
idWord.push_back(wordList[i]);
}
}

if(!wordId.count(endWord))
return {}; //不存在结束单词,返回空

if(!wordId.count(beginWord)){

wordId[beginWord] = id++; //加入起始单词
idWord.push_back(beginWord);
}


//构造图
edges.resize(id);
for(int i = 0; i < idWord.size(); i++){

for(int j = i + 1; j < idWord.size(); j++){

if(check_transform(idWord[i], idWord[j])){

edges[i].push_back(j);
edges[j].push_back(i); //构造两条有向边
}
}
}

int endWord_id = wordId[endWord];
vector<vector<string>> res;
queue<vector<int>> q;
q.push(vector<int>{wordId[beginWord]}); //起始单词作为一个路径入队

//cost[id]:从起始单词出发,转换到id所代表的单词所需的次数(代价)
vector<int> cost(id, INT_MAX);
cost[wordId[beginWord]] = 0;

while(!q.empty()){

vector<int> now_path = q.front();
q.pop();

int last_word_id = now_path.back();

//当前路径最后一个为结束单词时
if(last_word_id == endWord_id){

vector<string> temp;
for(int i = 0; i < now_path.size(); i++){

temp.push_back(idWord[now_path[i]]);
}
res.push_back(temp);
}
else{

for(int i = 0; i < edges[last_word_id].size(); i++){

//路径最后一个单词的连接单词
int next = edges[last_word_id][i];
if(cost[last_word_id] + 1 <= cost[next]){

cost[next] = cost[last_word_id] + 1; //更新转换次数

vector<int> temp(now_path.begin(), now_path.end());
temp.push_back(next);
q.push(temp);
}
}
}

}

return res;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: