欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

广度优先搜索:力扣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、题目描述:

广度优先搜索:力扣127. 单词接龙
广度优先搜索:力扣127. 单词接龙

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