题目描述
给出两个单词（start 和 end）和一个字典，找出从 start 到 end 的最短转换序列，输出最短序列的长度。
变换规则如下：
1、每次只能改变一个字母；
2、变换过程中的中间单词必须在字典中出现。(起始单词和结束单词不需要出现在字典中)
如果不存在这样的转换序列，返回 0；
所有单词具有相同的长度；
所有单词只由小写字母组成；
字典中不存在重复的单词。 你可以假设 beginWord 和 endWord 是非空的，且二者不相同
测试样例
输入：start = "a"，end = "c"，dict =["a","b","c"] 输出：2 解释： "a"->"c"
输入：start ="hit"，end = "cog"，dict =["hot","dot","dog","lot","log"] 输出：5 解释： "hit"->"hot"->"dot"->"dog"->"cog"
思路
使用双向 BFS，不仅仅在 start -> end 方向搜索，同时也在 end -> 方向搜索，理论上可减少平方量级的计算量。
具体方法
I. 初始化2个队列（可用 deque、set 等数据结构）q1、q2 分别用于两个方向的BFS，初始元素分别为 start 和 end，同时设置起始步数（作为序列长度）step = 1；
II. 循环条件是 q1 和 q2 均不为空，每循环一次 step 加1，每次先比较 q1 和 q2 的长度，把较短的队列赋值为 q1，每次仅对这个短的队列进行处理。另外，每次均初始化一个空队列 q_new，用于存储 BFS 的中间结果，即变换过程中的中间单词；
III. 取出 q1中位于头部的单词，对该单词的每个字母进行替换，每次替换1个，替换方式为从26个英文字母中枚举（除去和原有相同的）；
IV. 由于结束单词不必出现在字典中，于是先判断替换后的单词是否出现在另一队列 q2 中，若是，则返回当前步数；
V. 否则，若新单词出现在字典中，则将其加入II中的队列 q_new，同时在原字典中移除；
VI. 待 q1 中的单词都处理完后，将 q_new 赋值给 q1；
VII. 重复 II~VI 直至 找到解 或 q1 和 q2 有其中之一为空；
VIII. 当循环结束后仍未找到解，则说明不存在这样的转换序列，返回 0
代码
class Solution:
"""
@param: start: a string
@param: end: a string
@param: dict: a set of string
@return: An integer
"""
def ladderLength(self, start, end, dict):
q1, q2 = {start}, {end}
step = 1
while q1 and q2:
step += 1
# 每次仅对单词量较少的集合进行处理，令其为q1
if len(q1) > len(q2):
q1, q2 = q2, q1
# 存储变换过程中的中间单词
q_new = set()
for word in q1:
for i in range(len(word)):
new_words = self.find_new_words(word, i)
for new_word in new_words:
# 由于结束单词不必在字典中出现，
# 因此先判断是否已经变换为结束单词
if new_word in q2:
return step
# 变换过程中的中间单词必须在字典中出现
# 同时在原字典中移除
elif new_word in dict:
q_new.add(new_word)
dict.remove(new_word)
# 将中间变换过程存下的单词赋值给处理完的集合
q1 = q_new
return 0
def find_new_words(self, word, pos):
"""
对一个单词中指定位置的字母进行替换，
替换字母根据字母表枚举。
"""
new_words = []
prefix, suffix = word[:pos], word[pos + 1:]
for x in range(26):
new_alpha = chr(x + ord('a'))
# 忽略和当前要替换字母相同的字母
if new_alpha == word[pos]:
continue
new_word = prefix + new_alpha + suffix
new_words.append(new_word)
return new_words
网友评论