查看完整目录 –>《搞定算法与数据结构》

给定问题

来自：Letcode (127) – 课程表 2

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

• 序列中第一个单词是 beginWord 。
• 序列中最后一个单词是 endWord 。
• 每次转换只能改变一个字母。
• 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例1

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例2

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

解题思路

最短路径的问题，都可以使用广度优先的思路来解决。

第一步：数据预处理

给定的原始数据只有一个数组

wordList = ["hot","dot","dog","lot","log"]

要想使用广度优先的解法，第一步必须把已知数据，整理具体有如下图依赖关系的数据结构

假设用 map 来存储这一依赖关系，就需要用遍历来找到找有的可能性。

wordList = ["hot","dot","dog","lot","log","cog"]

def construct_dict():
    map = {}
    for word in wordList:
        for index in range(len(word)):
            s = word[:index] + "_" + word[index+1:]
            map[s] = map.get(s, []) + [word]
    return map

construct_dict()

将 map 打印出来，虽然存储内容与上面图中的并不完全相同，但可以达到的目的是一样的。

{
 '_og': ['dog', 'log', 'cog'],
 '_ot': ['hot', 'dot', 'lot'],
 'c_g': ['cog'],
 'co_': ['cog'],
 'd_g': ['dog'],
 'd_t': ['dot'],
 'do_': ['dot', 'dog'],
 'h_t': ['hot'],
 'ho_': ['hot'],
 'l_g': ['log'],
 'l_t': ['lot'],
 'lo_': ['lot', 'log']
}

第一轮

有了 map ，后面就可以从 beginWord = ‘hit’开始，遍历改变一个字符三种可能性：_it，h_t，hi_

再分别从 map 中找到所有符合的字符串，放入到一个队列 Q 中，若有找到，则转换次数加 1，并把该 beginWord 放入已访问的集合中，若无找到，直接返回 0。

第二轮

从上面的 Q 中，取出上一轮找到的字符串，对每个字符串 s ，同样遍历三种可能性 pattern，每一个可能性pattern，都去 map 中查找符合的字符串，若有的字符串已经访问过了，直接跳过，若还没有访问过，则再次放入 Q 中，并把 s 放入已访问的集合中。

往复轮回

重复以上步骤，直到找到某一个字符串刚好是目的的字符串，结束查找。

代码如下

def bfs(begin, target, d):
    queue, visited = [(begin, 1)], set()
    while len(queue) > 0:
        word, steps = queue.pop(0)
        if word not in visited:
            visited.add(word)
            if word == target:
                return steps
            for i in xrange(len(word)):
                s = word[:i] + "_" + word[i+1:]
                for j in d.get(s, []):
                    # 如果j在visited中，说明j已经被访问过了，不需要再次进行访问。
                    if j not in visited:
                        queue.append((j, steps+1))
    return 0

经验总结

使用广度优先算法解题，要准备：

• 已访问元素的集合，以便判断某些元素已经访问过了，重复访问永远不可能是最短路径
• 待访问元素的集合，以便一轮访问完成后，知道下一轮要访问哪些元素
• 能够直接或间接表示图结构的数据结构，如上面的 map