该算法的时间复杂度:词梯

查找从beginWord到的所有最短转换序列 结束语,这样:

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

例1:

endWord=“齿轮”, 字表= [“hot”,“dot”,“dog”,“lot”,“log”,“cog”]

输出:[[“命中”,“热”,“点”,“dog”,“cog”],[“hit”,“hot”,“lot”,“log”,“cog”]]

1) 从beginWord开始执行一个BFS,将每个字母转换成26个字母中的一个,然后查看转换后的单词是否在单词列表中,如果在,则放入队列中。

话

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)