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

变换规则如下：

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

ps

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

样例 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 

本周六还有系统设计免费讲座噢~

2 小时带你设计高频系统设计面试题——秒杀系统，全面解析高并发常见问题。 戳我免费报名

内容介绍：

通过秒杀系统和订票系统了解如下内容：

• 高并发场景下引发的常见问题
• 了解数据一致性
• 什么是动静分离
• 读写分离如何实现
• 如何防止超卖

讲师介绍

南帝——阿里在职 P7+，14 年+软件开发经验，10 年+架构设计经验，擅长系统整体架构方案设计，面试过超过 100+候选人，拥有多年资深面试官经验。

讲座时间：2020/7/18 本周六 上午 9:30:00

课程时长: 120 分钟

戳我免费报名