題目描述

題目鏈接：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)