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

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