1回答

liuyubobobo

2018-03-28

已采纳

这个问题的数据确实稍微有点而严，如果只使用BFS的话，尝试使用这两个思路优化一下试试看？

1） 

不要在广度优先遍历的时候在队列中存储单词和步数，在遍历过程中逐步判断从一个次是否能够达到另外一个词。而是在初始化的时候，对所有单词对进行一次这样的判断，生成一个无向图，之后再无向图上做广度优先遍历，就不需要再判断字符串之间的可达性了。这个思路可以参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/java-0127/src/Solution.java

2）

可以在广度优先遍历的时候用HashSet记录一下已经求出最短路径的点，对这些点，在后续广度优先遍历的时候不再考虑。对这个思路，可以参考代码：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/java-0127/src/Solution2.java

另外，这个问题数据这么严格，其实可以使用双向广度优先遍历来解决。我的两个课程均不涉及双向广度优先遍历，有兴趣可以自学一下，不过一般面试不会考。我的参考代码有两个版本的双向广度优先遍历解决这个问题：

版本1：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/java-0127/src/Solution3.java

版本2：https://github.com/liuyubobobo/Play-Leetcode/blob/master/0127-Word-Ladder/java-0127/src/Solution4.java

加油！

0

1

想不出来叫什么

真的太感谢您了！！！！！

2018-03-29

共1条回复