126. 单词接龙 II [hard]
126. 单词接龙 II [hard]
https://leetcode-cn.com/problems/word-ladder-ii/
给定两个单词（beginWord 和 endWord）和一个字典 wordList，找出所有从 beginWord 到 endWord 的最短转换序列。转换需遵循如下规则：
每次转换只能改变一个字母。 转换后得到的单词必须是字典中的单词。 说明:
- 如果不存在这样的转换序列，返回一个空列表。
- 所有单词具有相同的长度。
- 所有单词只由小写字母组成。
- 字典中不存在重复的单词。
- 你可以假设 beginWord 和 endWord 是非空的，且二者不相同。
示例 1:
输入:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
输出:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
示例 2:
输入:
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log"]
输出: []
解释: endWord "cog" 不在字典中，所以不存在符合要求的转换序列。
通过次数19,864 | 提交次数51,831
First Try
2020-06-27
又是一道初看起来完全没有想法的题目，不过昨晚做过127之后，这道题我以为已经手到擒来，结果tmd花了一整天的时间，从早上一直到现在下午五点了（虽然中间也是各种划水）。
一直无法处理的是如何记录多条可能的路径？在127题的解法中，只需要得到最短次数，写法都是按照直接短路跳出。本来改造了队列中的元素用来记录走过的路径，类似dict(list)的结果，但是没想到一个node其实有多种等价的路径可以到达，这个就尴尬了。
看了题解，才知道队列中可以使用列表作为元素，列表中最后一个元素作为node，这样就允许一层中有相同的node存在。
选用了单向BFS，在visited的处理部分也有些tricks和坑，搞定后终于顺利通过，排名还不错。
然后还是想走一波双向BFS，怎么搞都搞不定，非常纠结。按照我的写法太多琐碎的边界条件了，一直没法解决。看别人的题解，思路不一样的实在不想去仔细看，花了几个小时还是放弃吧，这双向BFS。
算是半天又解决了一道hard模式的“图”，开启新的边界。
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
if endWord == beginWord:
return [endWord]
if endWord not in wordList:
return []
if beginWord not in wordList:
wordList.append(beginWord)
# setup graph, words with maximum one char difference allowed
# 超时版本，还是超时了
# wlen = len(endWord)
# graph = {w: set() for w in wordList}
# for i in range(len(wordList)):
# for j in range(len(wordList)): # 不能改成range(i + 1, len(wordList))，必须双向
# c = 0
# for k in range(wlen):
# if wordList[i][k] != wordList[j][k]:
# c += 1
# if c > 1:
# break
# if c <= 1:
# graph[wordList[i]].add(wordList[j])
# graph[wordList[i]].remove(wordList[i])
# print(graph)
# speed up version for setup
wlen = len(endWord)
mixed = collections.defaultdict(set)
graph = {w: set() for w in wordList}
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
mixed[tmp].add(word)
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
graph[word].update(mixed[tmp])
graph[word].remove(word)
## BFS again
start_q = [(1, [beginWord])]
visited = dict()
rv = []
marked_level = 0
while len(start_q):
level, seq = start_q.pop(0)
if marked_level and marked_level < level:
break
node = seq[-1]
for n in graph[node]:
# 需要判断已经visited，但是为了保存多种可能，多种路径也能够走到同一个元素，该元素会被提前标记visited
if n in visited and level > visited[n]: # ??? 必须使用>号， 大于已经执行过的版本，没有意义；等于的话还可能在同一层
continue
# 如果不进行level判断，会出现bug
# if n in visited:
# continue
if n != endWord:
start_q.append((level + 1, seq + [n]))
else:
rv.append(seq + [n])
marked_level = level
visited[n] = level
return rv
# # BFS -- failed for dealing with multi-choice
# start_q = [(1, beginWord)]
# start_visited = collections.defaultdict(list)
# start_visited[beginWord] = []
# marked_level = 0
# rv = []
# print(graph)
# while (len(start_q)):
# level, node = start_q.pop(0)
# print(level, node, graph[node])
# # if marked_level and marked_level < level:
# # return rv
# for n in graph[node]:
# # bug version
# # if n in start_visited:
# # if n == endWord:
# # print("wtf", node, n, endWord)
# # continue
# # start_visited[n] = start_visited[node] + [node]
# # start_q.append((level + 1, n))
# if n not in start_visited:
# start_visited[n] = start_visited[node] + [node]
# start_q.append((level + 1, n))
# if n == endWord:
# print("hola", start_visited, n, node, endWord)
# rv.append(start_visited[n] + [n])
# marked_level = level
# return rv
# 写得一团乱的双向BFS版本
# end_q = [(1,endWord)]
# end_visited = collections.defaultdict(list)
# end_visited[endWord] = []
# rv = []
# marked_start = marked_end = 0
# start_level = end_level = 1
# while len(start_q) and len(end_q):
# start_level, node = start_q.pop(0)
# # print("start", node, start_level, end_level, marked_len)
# if marked_start and start_level > marked_start:
# return rv
# for n in graph[node]:
# if n not in start_visited:
# start_visited[n] = start_visited[node] + [node]
# start_q.append((start_level + 1, n))
# if n in end_visited:
# t = start_visited[n] + [n] + end_visited[n]
# if (not rv) or (rv and len(rv[-1]) == len(t)):
# rv.append(t)
# marked_start = start_level
# # print(start_visited[n], [n], end_visited[n])
# # print(rv)
# # print(start_visited)
# # start_level += 1
# end_level, node = end_q.pop(0)
# # print("end", node, start_level, end_level, marked_len)
# if marked_end and end_level> marked_end:
# return rv
# # if marked_len and start_level + end_level > marked_len:
# # return rv
# for n in graph[node]:
# print(node, n)
# if n not in end_visited:
# end_visited[n] = [node] + end_visited[node]
# end_q.append((end_level + 1, n))
# if n in start_visited:
# t= start_visited[n] + [n] + end_visited[n]
# if (not rv) or (rv and len(rv[-1]) == len(t)):
# rv.append(t)
# # marked_len = len(rv[-1])
# # marked_start = len(start_visited[n])
# marked_end = end_level
# # print(rv)
# print(start_visited[n], [n], end_visited[n])
# print(rv)
# print(start_visited)
# print(end_visited)
# # end_level += 1
# print("***")
# # if len(rv):
# # return rv
# return list(set(rv))
# def bfs(q, visited, other_visited, graph, rv):
# node = q.pop(0)
# for n in graph[node]:
# if n in other_visited:
# rv.append([node, n] + other_visited[n])
# if n not in start_visited:
# start_visited[n].insert(0, node)
# start_q.append(n)
- 执行用时：236 ms, 在所有 Python 提交中击败了71.37%的用户
- 内存消耗：22.8 MB, 在所有 Python 提交中击败了100.00%的用户
Failed Double BFS version
双向BFS实在太麻烦了，有各种tricks边界条件需要处理。
比如使用start visited和end vistied的话，如果发现已经在对面存在过，如何获取对面可能的多条路径，这又很头疼了。没有合适的数据结构，在visited中保存多条路径，同时快速索引。或者可以使用dict(list)结构？
还有就是如果两边同时相向而行，如果之间仅间隔一层，同时往前迈一步就错过了，悲剧。
## double BFS
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
if endWord == beginWord:
return [endWord]
if endWord not in wordList:
return []
if beginWord not in wordList:
wordList.append(beginWord)
# setup graph, words with maximum one char difference allowed
# speed up version for setup
wlen = len(endWord)
mixed = collections.defaultdict(set)
graph = {w: set() for w in wordList}
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
mixed[tmp].add(word)
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
graph[word].update(mixed[tmp])
graph[word].remove(word)
## BFS again, 双向不好写啊
## 改变每次循环中，先处理start再处理end的方法，改为直接同时
start_q = [[beginWord]]
end_q = [[endWord]]
rv = []
start_visited = set()
end_visited = set()
while len(start_q) and len(end_q):
slen = len(start_q)
elen = len(end_q)
sseq = []
sset = set()
eseq = []
eset = set()
for i in range(slen):
startn = start_q[i][-1]
if startn in start_visited:
continue
for j in range(elen):
endn = end_q[i][0]
# 属于上一轮的visited
if endn in end_visited:
continue
for sn in graph[startn]:
for en in graph[endn]:
if sn == en:
rv.append(start_q[i] + [sn] + end_q[i])
if not rv:
start_q.append(start_q[i] + [sn])
end_q.append([en] + end_q[i])
if rv:
return rv
for i in range(slen):
startn = start_q[i][-1]
start_visited.add(startn)
for j in range(elen):
endn = end_q[i][0]
end_visited.add(endn)
start_q = start_q[slen:]
end_q = end_q[elen:]
return rv
- another double bfs bug version
放弃了，还是没法搞出双向BFS的正确版本，太浪费时间了，这tmd都下午六点了，有这时间干点其他的不好？以后要限制一道题最多一个小时。
## double BFS
class Solution(object):
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
if endWord == beginWord:
return [endWord]
if endWord not in wordList:
return []
if beginWord not in wordList:
wordList.append(beginWord)
# setup graph, words with maximum one char difference allowed
# speed up version for setup
wlen = len(endWord)
mixed = collections.defaultdict(set)
graph = {w: set() for w in wordList}
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
mixed[tmp].add(word)
for word in wordList:
for i in range(wlen):
tmp = word[:i] + "*" + word[i+1: wlen]
graph[word].update(mixed[tmp])
graph[word].remove(word)
## BFS again, 双向不好写啊
## 改变每次循环中，先处理start再处理end的方法，改为直接同时
start_q = [[beginWord]]
end_q = [[endWord]]
rv = []
start_visited = collections.defaultdict(list)
end_visited = collections.defaultdict(list)
while len(start_q) and len(end_q):
current_visted = collections.defaultdict(list)
slen = len(start_q)
for i in range(slen):
startn = start_q[i][-1]
for node in graph[startn]:
if node not in start_visited:
current_visted[node].append(start_q[i] + [node])
if node in end_visited:
for seq in end_visited[startn]:
rv.append(start_q[i] + seq)
start_q.append(start_q[i] + [node])
if len(rv):
return rv
start_q = start_q[slen:]
start_visited.update(current_visted)
# tail queue
current_visited = collections.defaultdict(list)
elen = len(end_q)
for i in range(elen):
endn = end_q[i][0]
for node in graph[endn]:
if node not in end_visited:
current_visited[node].append([node] + end_q[i])
if node in start_visited:
for seq in start_visited[startn]:
rv.append(seq + end_q[i])
end_q.append([node] + end_q[i])
if len(rv):
return rv
end_q = end_q[elen:]
end_visited.update(current_visited)
return rv