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

问题:



我的解决方案基于此思想，但是如何分析此解决方案的时间和空间复杂性？

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是wordList中单词的数量。最糟糕的情况是，每个转换的单词都恰好在列表中，因此每个转换都需要26 * length of word。 DFS部分只是O(N)。因此，渐近只是O(L*N)
空间:O(N)

最佳答案

您不会找到所有简单的路径，因为结尾词可能会有其他最短的路径。最简单的反例如下:

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

您的算法将丢失路径aa -> ba -> bb。实际上，它最多只能找到一条路径。

时间复杂度的确是您编写时的O(L * N)，但空间复杂度是O(L*N)，这是图形或wordList占用的空间。

关于python - 该算法的时间复杂度: Word Ladder，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53075364/