讨论个题，word ladder 1.5（返回一条路径）

Lz看很多面试的帖子提到会问word ladder，但是只需要返回其中一条最短路径。
大家有什么好方法吗？

Lz觉得需要一个List<Set<String>>来记录每层的String，Map<String, String>，key是curString，value是preString。记录上一层的String。然后用map的string去List里的上一层去找。找到了加入path。

有更好的方法吗？

对于ladder II这种寻找path的题 如果求所有路径的是需要先bfs然后dfs，但是如果是只要一条最短路径，只需要一次bfs。具体来说在bfs的过程中，在把下一层节点i加入queue的时候，用一个map记录，key是下一层节点i的id, value是本层的节点id。这样到最后，就可以从结束点开始往前找parent，一直找到开头的点。因为加入queue的过程就是确定下一层点的parent的过程，所以每个点只进入queue一次，这个用set来保证。我说的这个只是针对输出一个最短path的解法，不过感觉现在确实好多面经是输出一条，个人感觉这样面试官更好看，输出那么多他也看不完~~

rabbitW 发表于 2017-1-22 11:22
对于ladder II这种寻找path的题 如果求所有路径的是需要先bfs然后dfs，但是如果是只要一条最短路径，只需要 ...

嗯，理解了。之前没想到可以用set来保证每个点只进入queue一次。觉得往回调用的时候可能会有远路。。。

多谢大家给的大米！！！受宠若惊

rabbitW 发表于 2017-1-22 11:22
对于ladder II这种寻找path的题 如果求所有路径的是需要先bfs然后dfs，但是如果是只要一条最短路径，只需要 ...

谢谢，我snapchat应该就跪在这里

Cats881119 发表于 2017-2-5 06:44
谢谢，我snapchat应该就跪在这里

我能说我是跪了snap之后，自己好好想了一下然后才发现这么做比较简洁

各位大神，请问一下，为啥leetcode上个月20号，
把输入参数从set变成了list？如果是遍历26个字母看是否在字典中，那得首先新建一个set来判断啊？
改成List莫非有巧妙之处？
请指点一下

yourdoraemon 发表于 2017-2-7 09:26
各位大神，请问一下，为啥leetcode上个月20号，
把输入参数从set变成了list？如果是遍历26个字母看是否在 ...

同问，而且改成list之后为何不需要把start和end先加入了？