Description
Given two words (start and end), and a dictionary, find all shortest transformation sequence(s) from start to end, output sequence in dictionary order.
Transformation rule such that:
Only one letter can be changed at a time
Each intermediate word must exist in the dictionary
All words have the same length.
All words contain only lowercase alphabetic characters.
At least one solution exists.
Example
Example 1:
Input：start = "a"，end = "c"，dict =["a","b","c"]
Output：[["a","c"]]
Explanation：
"a"->"c"
Example 2:
Input：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"]
Output：[["hit","hot","dot","dog","cog"],["hit","hot","lot","log","cog"]]
Explanation：
1."hit"->"hot"->"dot"->"dog"->"cog"
2."hit"->"hot"->"lot"->"log"->"cog"
The dictionary order of the first sequence is less than that of the second.
思路：
这个题难点在于如何得到最短的路径，答案用了一种很巧妙的方法，就是先用bfs倒着走一遍得到每个单词离终点的最短距离，接着用dfs再从头搜索一遍，选下一个词时只要保证离终点的距离再缩短那么最后找到的一定是最短路径。
另外一个点是通过遍历26个字母结合dictionary得到每个word的后继word集合，进行搜索。
代码：
网友评论