十大猎头公司_个人博客网站教程_郑州seo线上推广系统_海外发布新闻

题目描述

题目链接：110. 字符串接龙

代码实现

import collectionsn = int(input())
beginStr, endStr = input().split()
strList = [input() for _ in range(n)]deque = collections.deque()		# 使用队列遍历结点
deque.append([beginStr, 1])		# 存储当前字符串和遍历的到第几个结点
visited = set()					# 存储是否访问过该节点，访问过则跳过
visited.add(beginStr)while deque:word, path = deque.popleft()    # 当前字母和目标字母只相差一个时候，跳出if sum(1 for a, b in zip(word, endStr) if a != b) == 1:print(path + 1)exit()# 遍历字典for next_word in strList:# 下一个字母被构建过边（相差一个时候，构建出边），则跳过if next_word in visited:continue                # 当前字母和下一个字母只相差一个时候，添加遍历cnt_distinct = sum(1 for a, b in zip(word, next_word) if a != b)if cnt_distinct == 1:visited.add(next_word)deque.append([next_word, path + 1])
# 遍历完所有节点，均为找到，则跳出            
print(0)

参考文章：超详细的层层递进三种优化及复杂度分析，附双向 BFS 的 PPT， (C++ / Python / Java / Kotlin)