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

Question

问题:

Given two words (beginWord and endWord), and a dictionary's word list, find all shortest transformation sequence(s) from beginWord to endWord, such that:

Only one letter can be changed at a time. Each transformed word must exist in the word list. Note that beginWord is not a transformed word.

Example 1:

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

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

我的解决方案就是基于这个思路，但是我该如何分析这个解决方案的时间和空间复杂度呢？

1) Perform a BFS starting at beginWord by transforming every letter to one of 26 letters, and see if the transformed word is in the wordList, if so, put in queue.

2) During BFS, maintain a graph of {word:nextWord} for all valid next words

3) When a nextWord reaches endWord, do a backtracking DFS (pre-order traversal) on the graph to get all paths.

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)

Answer 1

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

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

您的算法会错过路径 aa -> ba -> bb。事实上，它最多只能找到一条路径。

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