题目描述
给定两个单词（beginWord 和 endWord）和一个字典，找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则：
- 每次转换只能改变一个字母。
- 转换过程中的中间单词必须是字典中的单词。
说明:
- 如果不存在这样的转换序列，返回 0。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 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）。首先存储所有单词的所有可能的变种；从 beginWord 开始搜索；遍历当前单词的所有变种；如果有一个变种为 endWord 则直接返回结果。注：需判断单词是否被遍历过，因为求的是最小路径。
- 方法二：双向广度优先搜索。同时从 beginWord 和 endWord 开始遍历，可以大大的节省时间。结束条件变为：当前单词的某个变种是否已经被另一个方向遍历过，如果被遍历过，则返回当前单词的层数与另一个方向变种单词的反方向层数。
代码
Python 3.6
方法一：广度优先搜索（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
| class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
length = len(beginWord)
word_change = {}
for word in wordList:
for i in range(length):
word_change.setdefault(word[:i] + "*" +word[i + 1:], []).append(word)
queue = [(beginWord, 1)]
visited = {beginWord: True}
while queue:
cur_word, level = queue.pop(0)
for i in range(length):
cur_word_change = cur_word[:i] + "*" + cur_word[i + 1:]
if cur_word_change not in word_change:
continue
for word in word_change[cur_word_change]:
if word == endWord:
return level + 1
if word not in visited:
visited[word] = True
queue.append((word, level + 1))
word_change[cur_word_change] = []
return 0
|
执行用时：164 ms
内存消耗：17.3 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
| class Solution:
def __init__(self):
self.word_change = {}
self.length = 0
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
self.length = len(beginWord)
for word in wordList:
for i in range(self.length):
self.word_change.setdefault(word[:i] + "*" +word[i + 1:], []).append(word)
queue_begin = [(beginWord, 1)]
queue_end = [(endWord, 1)]
visited_begin = {beginWord: 1}
visited_end = {endWord: 1}
res = None
while queue_begin and queue_end:
res = self.visited_node(queue_begin, visited_begin, visited_end)
if res is not None:
return res
res = self.visited_node(queue_end, visited_end, visited_begin)
if res is not None:
return res
return 0
def visited_node(self, queue, visited, others_visited):
cur_word, level = queue.pop(0)
for i in range(self.length):
cur_word_change = cur_word[:i] + "*" + cur_word[i + 1:]
if cur_word_change not in self.word_change:
continue
for word in self.word_change[cur_word_change]:
if word in others_visited:
return level + others_visited[word]
if word not in visited:
visited[word] = level + 1
queue.append((word, level + 1))
return None
|
执行用时：140 ms
内存消耗：17.2 MB
参考
https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode