#|广度优先遍历BFS专题（ Leetcode127 单词接龙）
广度优先遍历BFS专题： Leetcode127 单词接龙 （想直接粘代码的，直接看第二个板块）
1. BFS建字典网络 首先想到的是用BFS进行搜索：就是先建立一个网络，两个字母之间“编辑距离”相差为1的，建立起链接（也就是写道邻接表里去）。
注：我还不太会用python的class这个数据结构，在这里我用的是字典来实现的
每个key下记录了邻接节点，点的颜色，当前点到beginWord的距离。
然后通过广度优先搜索，找到该点，就停止，然后输出距离就可以了。这个做法跑得很慢，跑第30个test就超时了。
def ladderLength_graph(beginWord, endWord, wordList):
def diff(word1, word2):
res = 0
for i in range(0, len(word1)):
if word1[i] != word2[i]:
res = res + 1
return res
def engraph(beginWord, endWord, wordList):
lst = [beginWord]
lst.extend(wordList)
Adj = dict()
length = len(lst)
for i in range(0, length):
Adj[lst[i]] = [[], "white", "inf"]
for i in range(0, length):
for j in range(i + 1, length):
if lst[j] not in Adj[lst[i]][0]:
if diff(lst[i], lst[j]) == 1:
Adj[lst[i]][0].append(lst[j])
Adj[lst[j]][0].append(lst[i])
return Adj
def BFS(beginWord, endWord, AdjList):
queue = [beginWord]
AdjList[beginWord][2] = 1
while queue:
node = queue[0]
if node == endWord:
return AdjList[node][2]
posterior = 0
for j in AdjList[node][0]:
if AdjList[j][1] == "white":
queue.append(j)
AdjList[j][1] = "gray"
AdjList[j][2] = AdjList[node][2] + 1
posterior = posterior + 1
AdjList[node][1] = "black"
queue.pop(0)
return 0
AdjList = engraph(beginWord, endWord, wordList)
if endWord not in AdjList:
return 0
res = BFS(beginWord, endWord, AdjList)
return res虽然他很慢，但他还是一个非常直观的解决方式。
2. 两个列表+一个字典的BFS解决方式 如果理解了第一个列表中的想法的话，第二个方法的思路也就特别简单了。就是在BFS中，我直接记录下
white， gray， black （包含不同颜色点的集合）其中black字典中，对应的key下记录了这个节点到beginWord的最短距离。def ladderLength(beginWord, endWord, wordList):
def connect(word1, word2):
res = 0
for i in range(0, len(word1)):
if word1[i] != word2[i]:
res = res + 1
if res > 1:
return False
return Trueif endWord not in wordList:
return 0
if beginWord in wordList:
wordList.remove(beginWord)
white = []
white.extend(wordList)
gray = [beginWord]
black = dict()
black[beginWord] = 1
while True:
if not gray:
return 0
break
current = gray[0]
i = 0
while i < len(white):
temp = white[i]
if connect(temp, current):
gray.append(temp)
black[temp] = black[current] + 1
if temp == endWord:
return black[temp]
del white[i]
else:
i = i + 1
del gray[0]
return black[endWord]【#|广度优先遍历BFS专题（ Leetcode127 单词接龙）】但是，这样做还是超时的！虽然它第30个例子终于过了我在spyder编译器上跑第30个例子，他整整跑了8秒。
3. 能够提交成功的方法：双端广搜 假设一个全满二叉树，如果要从根节点搜索到叶子节点，那需要O ( 2 N ) O(2^N) O(2N) 时间复杂度，其中N N N 为二叉树的层数。如果一个从根节点向下寻找，一个从叶子节点向上寻找，那至少可以减少O ( 2 N / 2 ) O(2^{N/2}) O(2N/2) 的时间复杂度。因为叶子节点向上只能搜索到自己的祖先节点。
在单词接龙中，我们只需要从两端搜索，直到遍历到相同的点即可。如果有相同的点，那么：左边距离+右边距离-1就是我们的目标：
D i s t a n c e = D l e f t + D r i g h t ? 1 Distance=D_{left}+D_{right}-1 Distance=Dleft?+Dright??1
Remark:
- 值得注意的是，再赋值的时候，需要用
copy函数，不然你在给两端赋值的时候，赋值的是地址，改变左边的同时，右边也会改变。因此引入一个copy模块进行复制操作。
import copy
import time
def ladderLength(beginWord, endWord, wordList):
def connect(word1, word2):
res = 0
for i in range(0, len(word1)):
if word1[i] != word2[i]:
res = res + 1
if res > 1:
return False
return Truewhite1 = copy.copy(wordList)
white2 = copy.copy(wordList)
if endWord not in white1:
return 0
if beginWord not in white2:
white2.append(beginWord)
if beginWord in white1:
white1.remove(beginWord)
white2.remove(endWord)
gray1 = [beginWord]
gray2 = [endWord]
black1 = dict()
black2 = dict()
black1[beginWord] = 1
black2[endWord] = 1
while True:
if not gray1:
return 0
if not gray2:
return 0
current1 = gray1[0]
current2 = gray2[0]
i = 0
while i < len(white1):
temp = white1[i]
if connect(temp, current1):
gray1.append(temp)
black1[temp] = black1[current1] + 1
if temp == endWord:
return black1[temp]
del white1[i]
else:
i = i + 1
del gray1[0]j = 0
while j < len(white2):
temp2 = white2[j]
if connect(temp2, current2):
gray2.append(temp2)
black2[temp2] = black2[current2] + 1
if temp2 == beginWord:
return black2[temp2]
del white2[j]
else:
j = j + 1
del gray2[0]
common = set(black1.keys()) & set(black2.keys())
if common:
key = list(common)[0]
return black1[key] + black2[key] - 1
return black1[endWord]if __name__ == "__main__":
beginWord = "hot"
endWord = "dog"
wordList = ["hot","dog","dot"]
start = time.time()
res = ladderLength(beginWord, endWord, wordList)
print("Result =", res)
end = time.time()
print("Running Time = ", end - start)提交结果：
执行时间：2408 ms
内存消耗： 12.7 MB
文章图片
推荐阅读
- 富裕的好处是对资源的优先占有
- JavaScript|JavaScript — 初识数组、数组字面量和方法、forEach、数组的遍历
- 笔记|C语言数据结构——二叉树的顺序存储和二叉树的遍历
- D016+8组田心+《吉田医生哈佛求学记》-优先做大石头事件
- for循环遍历数组
- 集合框架(集合嵌套存储和遍历元素的案例代码实现)
- LeetCode-102.|LeetCode-102. 二叉树的层序遍历
- 先序遍历 中序遍历 后序遍历 层序遍历
- map的简单使用(去重和遍历)
- 循环遍历JSON数据