给出两个单词(start和end)和一个字典,找出所有从start到end的最短转换序列
比如:
1、每次只能改变一个字母。
2、变换过程中的中间单词必须在字典中出现。
所有单词具有相同的长度。
所有单词都只包含小写字母。
给出数据如下:
start = "hit"
end = "cog"
dict = ["hot","dot","dog","lot","log"]
返回
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
根据每两个单词是否只差一个字母,进行建图,然后如下。
1.深搜 + 回溯 + 记忆化(记录每个节点到 终结点 的最短转换序列),超时啦。。。
2.通过广搜 计算出终结点到各个节点的最短距离(包括源节点到终结点的最短距离,也就是和 最短转换序列的长度对应)