广度优先搜索:力扣127. 单词接龙
程序员文章站
2022-06-15 12:45:37
1、题目描述:2、题解:BFS先建邻接表,然后进行BFSclass Solution(object): def ladderLength(self, beginWord, endWord, wordList): # BFS if endWord not in wordList or not endWord or not beginWord or not wordList: return 0 n = len(begin...
1、题目描述:
2、题解:
BFS
先建邻接表,然后进行BFS
整体思路如下:
1、先处理特殊情况
2、建立邻接表:
对于每一个单词,每一个字符都用“*”代替,称为通配单词,加入到哈希表的key中,value为该单词
3、设置一个队列,把(beginWord,1)加入到队列中,代表头个单词和层次(也就是长度)
4、设置一个已访问的哈希表,存储已经访问的单词和True(哈希表查找速度快)
5、遍历队列:
从队列中取出单词和level
遍历该单词的长度:
记录该位置的通配单词
在该通配单词的邻接表中遍历:
找到endWord:返回
如果不在visited中:
设置已访问
添加进队列中
把该位置的通配单词的邻接表设置为[]
如果都没找到,返回0
python代码如下:
class Solution(object):
def ladderLength(self, beginWord, endWord, wordList):
# BFS
if endWord not in wordList or not endWord or not beginWord or not wordList:
return 0
n = len(beginWord)
all_comb_dict = collections.defaultdict(list)
#预处理,建邻接表,key:通用字符串,value为wordList里的单词
for word in wordList:
for i in range(n):
all_comb_dict[word[:i] + '*' + word[i+1:]].append(word)
queue = [(beginWord,1)]
visited = {beginWord:True}
while queue:
current_word,level = queue.pop(0)
for i in range(n):
intermediate_word = current_word[:i] + '*' + current_word[i+1:]
for word in all_comb_dict[intermediate_word]:
if word == endWord:
return level + 1
if word not in visited:
visited[word] = True
queue.append((word,level+1))
all_comb_dict[intermediate_word] = []
return 0
3、复杂度分析:
时间复杂度:O(NM),N是单词的长度,M是字典中单词的数量
空间复杂度:O(NM)
本文地址:https://blog.csdn.net/weixin_42042056/article/details/107217306