[LeetCode]Word Ladder

这一题本质上是bfs的问题，我们要考虑的部分就是找响相邻节点的问题，我们对于每一位从a变到来看是不是在dict里，在的话就是相邻的节点，其他部分和bfs是一样的，我们记录一下扫到哪里碰到目标节点就行了，代码如下：

另外这一题如果要优化的话，可以考虑双向bfs，时间和空间都可以优化到O(b^(d / 2))，b是branch factor，d是起点和目标的距离。我们就在起点和终点一起开始bfs就行，起点一圈，终点一圈，直到

• 起点bfs访问到了到了终点bfs访问过的节点（终点的visited set）
• 终点bfs访问到了到了起点bfs访问过的节点（起点的visited set）
• 终点或者起点的queue为空（注意如果两个node真的是联通的，那么在check到相交的部分之前不会为空）

优化的部分就考虑可以先继续搜queue size较小的那边，这样可以更节省空间，时间上也会一定程度优化，不过这只是有限的优化，不会影响时间复杂度，代码如下：