亚马逊面试高频题：单词接龙Ⅱ

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 1393 天前的主题，其中的信息可能已经有所发展或是发生改变。

给出两个单词（start和end）和一个字典，找出所有从start到end的最短转换序列。

变换规则如下：

每次只能改变一个字母。
变换过程中的中间单词必须在字典中出现。

所有单词具有相同的长度。
所有单词都只包含小写字母。
题目确保存在合法的路径。

样例 1:

输入：start = "a"，end = "c"，dict =["a","b","c"]
输出：[["a","c"]]
解释：
"a"->"c"

样例 2:

输入：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
输出：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
解释：
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
第一个序列的字典序小于第二个。

** [题解] **

算法：BFS+DFS

题目要求找出所有从start到end的最短转换序列，显然我们需要考虑bfs搜索最短路，路径中的下一跳都存在于字典内，由于都是小写字母，可以枚举当前字符串下一跳可能的所有字符串,对于字符串s,将他的每一位都用'a'-'z'替换一遍，判断被替换字母后的s是否存在于dict中,这样相比直接在dict中搜索下一跳可以有效的减少时间复杂度（如果直接找下一跳那么必须遍历dict）。跑完所有最短路径后再 dfs 将图转换为start--end的路径

先添加end到dict中，便于计算
先对start--end通过队列bfs计算出所有最短路
对于每个当前字符串用暴力替换每一位的字母，查找是否存在于dict中
通过dfs遍历所有最短路，打印出所有路径

复杂度分析

时间复杂度O((V+E))
bfs O(V+E)遍历所有边 E（即当前字符串的下一跳）和点V，dfsO(size(dict))跑最后的最短路
空间复杂度O(size(dict)*k)
存每个字符串与下一跳字符串的集合以及最短路径

class Solution:
    """
    @param: start: a string
    @param: end: a string
    @param: dict: a set of string
    @return: a list of lists of string
    """
    def findLadders(self, start, end, dict):
        from collections import defaultdict
        dict = set(dict)
        #将 end 添加进 dict,防止结果为[]
        dict.add(end)
        res = []
        # 记录单词下一步能转到的单词
        next_word_dict = defaultdict(list)
        # 记录到 start 距离
        distance = {}
        distance[start] = 0

        # 暴力匹配,当前字符串修改一个字母后的新字符串存在于 dict 中
        def next_word(word):
            ans = []
            for i in range(len(word)):
                       #97=ord('a')，123=ord('z')+1  
                for j in range(97, 123):
                    tmp = word[:i] + chr(j) + word[i + 1:]
                    if tmp != word and tmp in dict:
                        ans.append(tmp)
            return ans
        # 求到 start 的距离
        def bfs():
            q = collections.deque()
            q.append(start)
            step = 0
            flag = False #标记是否找到结果
            while len(q) is not 0:
                step += 1
                n=len(q)
                for i in range(n):
                    word=q[0]
                    q.popleft()
                    for nextword in next_word(word):
                        next_word_dict[word].append(nextword)
                       #当下一跳是 end 时，就可以结束搜索
                        if nextword == end:
                            flag = True
                        #如果没被添加过，则进行添加
                        if nextword not in distance:
                            distance[nextword] = step
                            q.append(nextword)
                if flag:
                    break
        # 遍历所有从 start 到 end 的路径
        def dfs(tmp, step):
            if tmp[-1] == end:
                res.append(tmp)
                return
            for word in next_word_dict[tmp[-1]]:
                if distance[word] == step + 1:
                    dfs(tmp + [word], step + 1)
        #bfs 搜 start--end 的最短路径           
        bfs()
        #dfs 输出距离最短的路径
        dfs([start], 0)
        return res