leetcode 127. 单词接龙
题目：127. 单词接龙
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,返回它的长度 5。
示例1:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]
输出: 5
解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,返回它的长度 5。
示例2:
输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”]
输出: 0
解释: endWord “cog” 不在字典中，所以无法进行转换。
方法一：BFS（广度优先搜索）
思路：BFS（广度优先搜索），将当前单词只改变一个字母的所有单词都视为可扩展搜索的方向，通过判断改变的单词是否在词库中，选择是否将其扩展入队（在词库中则入队）。直至扩展到endWord（此时说明已搜索到目标数），或者队列为空（此时说明无法搜索到目标数），则搜索结束。Set检索元素效率低下，删除和插入效率高；List查找元素效率高，插入删除元素效率低。但是若用contains方法查询对象元素，Set集合应该比List效率要高，所以将词库wordList转成Set，以提高效率。
运行数据：执行用时：64 ms，内存消耗：41.6 MB
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
|
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
int result = 0;
HashSet<String> words = new HashSet<>(wordList);
Queue<String> queue = new LinkedList<String>();
queue.offer(beginWord);
int queueLen = 1;
while (queueLen > 0) {
int currentQueueLen = queueLen;
result++;
words.removeAll(queue);
while (currentQueueLen-- > 0) {
String currentString = queue.poll();
queueLen--;
char[] chars = currentString.toCharArray();
for (int i = 0; i < chars.length; i++) {
char temp = chars[i];
for (char j = 'a'; j <= 'z'; j++) {
chars[i] = j;
String word = new String(chars);
if (words.contains(word)) {
if (word.equals(endWord)) {
return result + 1;
}
queue.offer(word);
queueLen++;
}
}
chars[i] = temp;
}
}
}
return 0;
}
|
方法二：双向BFS（广度优先搜索）
思路：双向BFS（广度优先搜索），在上述基本BFS的基础上，进行该进。endWord为起点endWord为终点，用start、end分别记录从起点端向终点端的扩展单词和从终点向起点扩展的单词，一开始从起点向终点扩展，扩展一轮后如果当前的扩展单词数大于另一个方向的扩展单词数则改变方向，从终点往起点开始扩展。依次类推，根据这个规则改变搜索方向，直至当前方向的搜索搜索到另一个方向的扩展单词（此时说明已收索到目标数），或者当前搜索方向的扩展单词为空（此时说明无法搜索到目标数），则搜索结束。
运行数据：执行用时：11 ms，内存消耗：40.7 MB
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
|
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
HashSet<String> start = new HashSet<>();
start.add(beginWord);
HashSet<String> end = new HashSet<>();
end.add(endWord);
HashSet<String> words = new HashSet<>(wordList);
if (!words.contains(endWord)) {
return 0;
}
return bothwayBfs(start,end,words,2);
}
private int bothwayBfs(HashSet<String> start, HashSet<String> end, HashSet<String> words, int depth) {
if (start.size() > end.size()) {
return bothwayBfs(end, start, words, depth);
}
words.removeAll(start);
HashSet<String> next = new HashSet<>();
for (String str : start) {
char[] chars = str.toCharArray();
for (int i = 0; i < chars.length; i++) {
char temp = chars[i];
for (char j = 'a'; j <= 'z'; j++) {
chars[i] = j;
String word = new String(chars);
if (words.contains(word)) {
if (end.contains(word)) {
return depth;
}
next.add(word);
}
}
chars[i] = temp;
}
}
if (start.isEmpty()) {
return 0;
}
return bothwayBfs(next, end, words, depth + 1);
}
|
学习所得，资料、图片部分来源于网络，如有侵权，请联系本人删除。
才疏学浅，若有错误或不当之处，可批评指正，还请见谅！
