题目-困难难度
字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列 beginWord -> s1 -> s2 -> … -> sk：
每一对相邻的单词只差一个字母。
对于 1 <= i <= k 时，每个 si 都在 wordList 中。注意， beginWord 不需要在 wordList 中。
sk == endWord
给你两个单词 beginWord 和 endWord 和一个字典 wordList ，返回 从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0 。
示例
示例 1：
示例 2：
提示：
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/summary-ranges
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1. bfs
时间
388ms
击败 53.49%使用 Python3 的用户
内存
16.85MB
击败 76.93%使用 Python3 的用户
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# 将wordList去重
wordList = set(wordList)
# 如果查询的单词不存在于wordList中,直接返回0
if endWord not in wordList:
return 0
# 初始查询的单词
q = {beginWord}
# 初始化步骤, 最低为2
step = 2
# 遍历单词
while q:
# 用于存储下一次遍历单词
tmp = set()
# 对于q中的单词
for word in q:
# 依次遍历单词的每一个字母
for i in range(len(word)):
# 替换单词的当前字母为a-z中其他的字母
for c in 'abcdefghijklmnopqrstuvwxyz':
# 生成替换后的新单词
newWord = word[:i] + c + word[i+1:]
# 如果替换后的单词就是目标单词
if newWord == endWord:
# 返回最终步骤数
return step
# 如果不是目标单词, 但是存在于单词列表中
if newWord in wordList:
# 添加到下次遍历
tmp.add(newWord)
# 从单词列表中移除当前单词, 防止重复
wordList.remove(newWord)
# 给q赋值下次需要遍历的单词
q = tmp
# 步骤数+1
step += 1
# 未能找到则返回0
return 0
2. bfs
超出时间限制
class Solution:
def ladderLength(self, beginWord: str, endWord: str, wordList: List[str]) -> int:
# 判断两个单词是否只有一个不同的方法
def oneDiff(l1,l2):
return sum(i!=j for i,j in zip(l1,l2)) == 1
# 获取wordList长度
lwl = len(wordList)
# 创建列表存储相关联并且一字之差的单词
adj = [[] for _ in range(lwl)]
# 为获取目标索引初始化一个索引
endIndex = -1
# 遍历列表项
for i, s in enumerate(wordList):
# 如果当前单词为目标单词, 获取它的索引
if s == endWord:
endIndex = i
# 将每个单词相差一个单词的单词, 放到关联链表
for j in range(i + 1, lwl):
if oneDiff(s, wordList[j]):
adj[i].append(j)
adj[j].append(i)
# 如果查询的单词不存在于结果列表内, 返回0
if endIndex == -1:
return 0
# 遍历找出与查询单词相近的单词
q = [i for i, s in enumerate(wordList) if oneDiff(beginWord, s)]
# 存储遍历过的单词
vis = set(q)
# 如果第一个就找到, 说明转换序列的长度为2
step = 2
# 遍历开始
while q:
# tmp获取q列表
tmp = q
# 将q列表赋值为空方便添加下一级遍历的单词
q = []
# 遍历最相近的单词
for cur in tmp:
# 如果找到了目标单词, 返回步数
if cur == endIndex:
return step
# 如果没找到, 遍历当前相近单词下的第二层相近的单词
for nxt in adj[cur]:
# 确保单词未被遍历的情况下,添加下一次遍历的单词
if nxt not in vis:
vis.add(nxt)
q.append(nxt)
step += 1
return 0