图

LeetCode 127

输入:
beginWord = “hit”,
endWord = “cog”,
wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”]

输出: 5

解释: 一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”,
返回它的长度 5。

广度优先搜索

• 1. 构建邻接图，通用状态到单词的图

D*g —-> Dog,Dig
Map> allComboDict = new HashMap<>();

• 1. (beginWord, 1) 放入队列，..
• 1. 防止成环，用数组记录使用过的单词
• 1. 当队列中有元素的时候，取出第一个元素，记为 current_word。
• 1. 找到 current_word 的所有通用状态，并检查这些通用状态是否存在其它单词的映射，这一步通过检查 all_combo_dict 来实现。Dog —> og , Dg, Do* —-find—> allComboDict
• 1. 从 all_combo_dict 获得的所有单词，都和 current_word 共有一个通用状态，所以都和 current_word 相连，因此将他们加入到队列中。
• 1. 对于新获得的所有单词，向队列中加入元素 (word, level + 1) 其中 level 是 current_word 的层次。
• 1. 最终当你到达期望的单词，对应的层次就是最短变换序列的长度。

双向广度优先搜索

• 同时从beginWord和endWord开始搜索

算法与之前描述的标准广搜方法相类似。
唯一的不同是我们从两个节点同时开始搜索，同时搜索的结束条件也有所变化。
我们现在有两个访问数组，分别记录从对应的起点是否已经访问了该节点。
如果我们发现一个节点被两个搜索同时访问，就结束搜索过程。因为我们找到了双向搜索的交点。过程如同从中间相遇而不是沿着搜索路径一直走。
双向搜索的结束条件是找到一个单词被两边搜索都访问过了。
最短变换序列的长度就是中间节点在两边的层次之和。因此，我们可以在访问数组中记录节点的层次。