[LeetCode]127. 单词接龙(Word Ladder)

题目描述

给定两个单词(beginWord 和 endWord)和一个字典,找到从 beginWord 到 endWord 的最短转换序列的长度。转换需遵循如下规则:

  1. 每次转换只能改变一个字母。
  2. 转换过程中的中间单词必须是字典中的单词。 说明:
  • 如果不存在这样的转换序列,返回 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” 不在字典中,所以无法进行转换。

解题思路

  1. 方法一:广度优先搜索(BFS)。首先存储所有单词的所有可能的变种;从 beginWord 开始搜索;遍历当前单词的所有变种;如果有一个变种为 endWord 则直接返回结果。注:需判断单词是否被遍历过,因为求的是最小路径。
  2. 方法二:双向广度优先搜索。同时从 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 = {} # 用来存储单词的所有变种。key: 变种,val: 单词列表
for word in wordList:
for i in range(length):
word_change.setdefault(word[:i] + "*" +word[i + 1:], []).append(word)
queue = [(beginWord, 1)] # 用来存储当前层的所有节点。(word, 层数)
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