查找从beginWord到的所有最短转换序列
结束语,这样:
一次只能更改一个字母。每个被转换的单词必须
存在于单词列表中。请注意,beginWord不是一个经过转换的单词。
例1:
endWord=“齿轮”,
字表=
[“hot”,“dot”,“dog”,“lot”,“log”,“cog”]
输出:[[“命中”,“热”,“点”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]
1) 从beginWord开始执行一个BFS,将每个字母转换成26个字母中的一个,然后查看转换后的单词是否在单词列表中,如果在,则放入队列中。
话
3) 当nextWord到达endWord时,执行回溯DFS(预订购
遍历)在图上获取所有路径。
class Solution:
def findLadders(self, beginWord, endWord, wordList):
"""
:type beginWord: str
:type endWord: str
:type wordList: List[str]
:rtype: List[List[str]]
"""
wordListSet = set(wordList+[beginWord])
graph = collections.defaultdict(list)
q = set([beginWord])
count = 0
result = []
while q:
count +=1
newQ = set()
for word in q:
wordListSet.remove(word)
for word in q:
if word == endWord:
self.getAllPaths(graph, beginWord, endWord, result, [])
return result
for i in range(len(word)):
for sub in 'abcdefghijklmnopqrstuvwxyz':
if sub != word[i]:
newWord = word[:i] + sub + word[i+1:]
if newWord in wordListSet:
graph[word].append(newWord)
newQ.add(newWord)
q = newQ
return []
def getAllPaths(self, graph, node, target, result, output):
#This is just a backtracking pre-order traversal DFS on a DAG.
output.append(node)
if node==target:
result.append(output[:])
else:
for child in graph[node]:
self.getAllPaths(graph,child, target, result, output)
output.pop()
我的论点是:
时间:
O(26*L*N + N
),其中
L
是
平均长度
每一个字,以及
N
字表中的字数
. 这里最坏的情况是,转换后的每个单词恰好都在列表中,因此每个转换都需要
26 * length of word
. DFS部分只是
O(N)
O(L*N)
间距:O(N)