题目描述： 今天说的单词接龙不是传统意义上的单词接龙。我们的游戏如下： 给你两个词，a和b，现在请你经过一系列转换，将a转换成b。 转换规则：每个词在转换的时候，只能修改其中一个字母（不能删除或者插入）， 转换过程中得到的词必须是正确的词（在词典中存在的词） 例如：我们想把单词spice转换成stock，可能的一个转换序列为： spice -> slice -> slick -> stick -> stock, 一共需要四步。 现在给你一个词典L，L中定义了所有合法的单词，L是一个由字符串构成的列表； 同时给你两个单词a和b，请你计算从a转换到b至少需要经过多少步。 若无法成功转换，则输出-1. 如： L = [‘spice’, ‘slice’, ‘slick’, ‘stick’, ‘stock’, ‘ipad’] a = ‘spice’, b = ‘stock’, 则输出4
示例：
1
2
3
4
5
6
输入：
L = ["dip", "lip", "mad", "map", "maple", "may", "pad", "pip", "pod", "pop", "sap", "sip", "slice", "slick", "spice", "stick", "stock"]
a = "spice"
b = "stock"
输出：
4
分析: 因为我们只能删除或者是修改某一个单词，所以说如果长度不一样，那就肯定是无法转换的。
然后把列表里面和 a, b 长度不一样的字符串全部去除掉。
最后我们使用类似广度优先的方式进行搜索，每次遍历整个列表，再判断遍历的时候判断每个字符串和当前字符串的不相同字符串有多少？
如果刚好为1个，那就放入队列，并且将步数加1。最后我们就可以得到到达 b 所需要的步骤数了。
代码:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
if len(a) != len(b):
print(-1)
# 去掉长度 不一样的其他字符串，减少搜索空间
len_a = len(a)
L = [item for item in L if len(item)==len_a]
L.remove(a)
from queue import Queue
L_set = set()
L_set.add(a)
L_dict = {a:0}
que = Queue()
que.put(a)
while not que.empty():
item = que.get()
for temp in L:
if temp in L_set:
continue
d = 0
for i in range(len_a):
if temp[i] != item[i]:
d += 1
if d == 1 and temp not in L_set:
que.put(temp)
L_dict[temp] = L_dict[item] + 1
L_set.add(temp)
print(L_dict.get(b, -1))