描述
给出两个单词（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"从 end 到 start 做一次 BFS，并且把距离 end 的距离都保存在 distance 中。 然后在从 start 到 end 做一次 DFS，每走一步必须确保离 end 的 distance 越来越近。
与另外一个代码中提前建立 index 不同，这里是在寻找下一个变换单词的时候，再去获得对应的单词列表。一个单词最多有 L 个字符，每个字符有 25 种不同的变化（26个字母除掉这个位置上的字母），然后 check 一下在不在 dict 里就知道是不是 next word 了。
from collections import deque
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):
dict.add(start)
dict.add(end)
distance = {}
self.bfs(end, distance, dict)
results = []
self.dfs(start, end, distance, dict, [start], results)
return results
def bfs(self, start, distance, dict):
distance[start] = 0
queue = deque([start])
while queue:
word = queue.popleft()
for next_word in self.get_next_words(word, dict):
if next_word not in distance:
distance[next_word] = distance[word] + 1
queue.append(next_word)
def get_next_words(self, word, dict):
words = []
for i in range(len(word)):
for c in 'abcdefghijklmnopqrstuvwxyz':
next_word = word[:i] + c + word[i + 1:]
if next_word != word and next_word in dict:
words.append(next_word)
return words
def dfs(self, curt, target, distance, dict, path, results):
if curt == target:
results.append(list(path))
return
for word in self.get_next_words(curt, dict):
if distance[word] != distance[curt] - 1:
continue
path.append(word)
self.dfs(word, target, distance, dict, path, results)
path.pop()
