给定两个单词(start, end)和一个字典，要求找出从单词start变化到end的最小序列。变化过程中出现的中间单词必须是字典中有的单词，且每次只能是变化其中的一个字母。 比如start= “hit”, end= “cog”, dict = [“hot”, “dot”, “dog”, “lot”, “log”]。 那么从start变化到end经过了5步，即"hit"→"hot" →"dot" →"dog"→"cog"。
# _*_ coding=utf-8 _*_ __author__ = 'SRF' __date__ = '2019/5/26 8:05' # 字梯问题 ''' 将单词和与其相差一个字符的单词之间构造边 构造无向图 利用宽搜计算两点间最短路径 ''' from collections import defaultdict class BFSResult: def __init__(self): self.level = {} self.parent = {} # 最短路径 def find_shortest_path(r, v): path = [v, ] # 获得源点 source_vertex = [vertex for vertex, level in r.level.items() if level == 0][0] if v != source_vertex: while r.parent[v] != source_vertex and r.parent[v] is not None: v = r.parent[v] path.append(v) path.append(source_vertex) path.reverse() return path class Graph(): def __init__(self): self.adj = defaultdict(list) def add_edge(self, u, v): for w in v: if w in self.adj[u] or len(w) != len(u): continue match = [i for i in range(len(u)) if w[i] == u[i]] # 存储相同字符的索引 if len(match) == len(u) - 1: # 若相同字符为字符串长度减一 符合变化要求 构造边 self.adj[u].append(w) self.adj[w].append(u) def bfs(g, s): # 图 初始节点 r = BFSResult() r.level = {s: 0} r.parent = {s: None} i = 1 # 记录层编号 012 frontier = [s] while frontier: next = [] for u in frontier: for v in g.adj[u]: if v not in r.level: r.level[v] = i r.parent[v] = u next.append(v) frontier = next i += 1 return r if __name__ == '__main__': g = Graph() dict = ["hot", "dot", "dog", "lot", "log"] start = "hit" end = "cog" dict.extend([start, end]) # 将起始点加入dict 否则构造的图不完整 for i in dict: g.add_edge(i, dict) r = bfs(g, start) print(start + "到" + end + "的最短路径为") print(find_shortest_path(r, end))