Вопрос:
С учетом двух слов (beginWord и endWord) и списка слов в словаре,
найти все кратчайшие последовательности преобразования из beginWord в
endWord, такой что:
Одновременно можно изменить только одну букву. Каждое преобразованное слово должно
существуют в списке слов. Обратите внимание, что beginWord не является преобразованным словом.
Пример 1:
Ввод: beginWord = "hit",
endWord = "винтик",
wordList =
[ "Горячая", "точка", "собака", "много", "журнал", "винтик"]
Вывод: [["hit", "hot", "dot", "dog", "cog"], ["hit", "hot", "lot", "log", "cog"]]
Мое решение основано на этой идее, но как мне проанализировать временную и пространственную сложность этого решения?
1) Выполните BFS, начиная с beginWord, преобразовав каждую букву в одну из 26 букв, и посмотрите, есть ли преобразованное слово в списке слов, если это так, поместите в очередь.
2) Во время BFS ведите график {word: nextWord} для всех действительных следующих
слова
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)