该算法的时间复杂度:Word Ladder

Question

题:

给定两个单词(beginWord和endWord)和一个字典的单词列表,找到从beginWord到endWord的所有最短变换序列,这样:

一次只能更改一个字母.每个转换后的单词必须存在于单词列表中.请注意,beginWord不是转换后的单词.

例1:

输入:beginWord ="hit",endWord ="cog",wordList = ["hot","dot","dog","lot","log","cog"]

输出:[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]

我的解决方案基于这个想法,但我如何分析此解决方案的时间和空间复杂性？

1)通过将每个字母转换为26个字母中的一个来执行从beginWord开始的BFS,并查看转换后的单词是否在wordList中,如果是,则放入队列.

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)

Answer 1

您将找不到所有简单路径,因为可能存在到结束词的替代最短路径.最简单的反例如下:

beginWord = aa,
endWord = bb
wordList = [aa, ab, ba, bb]

你的算法会错过这条路aa -> ba -> bb.事实上,它总会找到最多一条路径.

时间的复杂性确实O(L * N)与你所写的一样,但空间复杂性是O(L*N)你的图形或wordList占据的空间.