链接: https://leetcode-cn.com/problems/word-ladder-ii/description/
题意
给定一个起始字符串和一个终止字符串,以及一个单词表,求是否可以将起始字符串每次改一个字符,直到改成终止字符串,且所有中间的修改过程表示的字符串都可以在单词表里找到。
输出需要修改次数最少的所有更改方式
解法
本题的难度是Hard,难点在于搜索过程中的优化
我们可以将这道题抽象成一个图,每个单词就是图中的一个结点
如果两个字符串只有一个字母不同,则这两个结点之间有一条边相连
建图的过程使用广度优先搜索,在建完以后进行回溯找出所有的路径
在实现上也有一些难点和可以学习的地方,代码也做了详细的注释
例如使用一个数组标记是否入队,遍历整个队列的for循环处理
有一个重点是,需要将图建成一个有向图
由于是BFS,所以会将队列中所有元素全拿出来进行建图,为了不产生走回头路的情况
结点之间只会是单项边
如果一个结点已经被访问过了,它就会被从单词表中去除
为了查找的高效,将单词表转成set进行处理
有一些count, erase和find的操作也需要熟练
在找某个字符串所有的邻居时,除了遍历所有字符串以外,还可以替换单词中的每一个字符,在单词表大的情况下可以降低计算复杂度
BFS建图完成后回溯完成路径的匹配,这是针对这一题而言的
对于单词接龙这一题而言,由于其只需要找到最短的路径长度,所以在BFS过程中只要找到目标字符串就可以结束
代码
126 单词接龙II
1 | class Solution { |
v1.5.2