小编ven*_*lac的帖子

题:

给定两个单词(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)): …