时间戳

首页 > 解决方案 > 该算法的时间复杂度：Word Ladder

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

问题描述

问题：

给定两个单词（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) 从 beginWord 开始执行 BFS，将每个字母转换为 26 个字母之一，并查看转换后的单词是否在 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()

我很难想出它的时间和空间复杂性。我的论点：

Time: O(26*L*N + N)，其中L是每个单词的平均长度N，是wordList 中的单词数。这里最坏的情况是每个转换的单词都恰好在列表中，所以每个转换都需要26 * length of word. DFS 部分只是O(N). 所以渐近地它只是O(L*N)

空间：O(N)

标签： pythontime-complexitybreadth-first-search

解决方案

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

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

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

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

推荐阅读