1回答

liuyubobobo

2018-04-23

已采纳

可以参考这里：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0126-Word-Ladder-II/cpp-0126/main.cpp

整体思路是，由于要找到所有解，所以不能再bfs中记录步数直接返回。因此在bfs的过程中，维护一个叫做distance的map，记录从begin到每一个单词的最短路径。最后根据这个distance，回溯搜索一遍，找到所有的解。

P.S.1 这个问题测试用例卡的有点儿紧，我尝试生成的图g使用邻接矩阵会超时；使用邻接表可以获得通过。

P.S.2 由于127号问题可以使用双端搜索解决，所以这个问题也可以使用双端搜索解决（而且应该效率更高）。不过由于双端搜索本身在这个课程中没有涉及（面试中也很少会考到），我时间有限，先不在这里给126的双端搜索的解了。关于127号问题，如果对双端搜索的实现感兴趣，可以参考这里。其中main3和main4的解法为双端搜索：https://github.com/liuyubobobo/Play-Leetcode/tree/master/0127-Word-Ladder/cpp-0127

加油！：）

0

1

想不出来叫什么

非常感谢！

2018-04-23

共1条回复