这是问题描述:
给出两个单词(beginWord和endWord),以及字典的单词列表,查找从beginWord到的所有最短转换序列endWord,例如:
一次只能更改一个字母,每个转换的单词必须存在于单词列表中。请注意,beginWord不是转换后的单词。
注意:
如果没有这样的转换序列,请返回一个空列表。所有单词的长度相同。所有单词仅包含小写字母字母字符。您可以假设单词列表中没有重复项。您可以假设beginWord和endWord不是空的,并且不是一样。
测试用例:
Input:
beginWord = "hit",
endWord = "cog",
wordList = ["hot","dot","dog","lot","log","cog"]
Output:
[
["hit","hot","dot","dog","cog"],
["hit","hot","lot","log","cog"]
]
我的问题:
为了跟踪遍历到达当前节点所需的路径,我试图传递一个路径数组,该路径数组在每次将新节点添加到队列时都进行更新。当前,更新路径的代码为:q.append((word, level + 1, previous + [top]))
。由于某种原因,我的路径数组实际上并不是每次都在更新。我做错了什么?
我的代码:
import collections
class Solution:
def findLadders(self, beginWord: str, endWord: str, wordList: List[str]) -> List[List[str]]:
representations = {}
for word in wordList:
for i in range(len(word)):
rep = word[:i] + "_" + word[i+1:]
if word[:i] + "_" + word[i+1:] in representations:
representations[rep].append(word)
else:
representations[rep] = [word]
q = collections.deque()
q.append((beginWord, 0, []))
shortest = 0
result = []
visited = {}
while q:
top, level, previous = q.popleft()
if top in visited: continue
if not found:
if top == endWord:
found = True
result.append(path)
shortest = level
else:
visited[top] = True
for i in range(len(top)):
rep = word[:i] + "_" + word[i+1:]
for word in representations[rep]:
q.append((word, level + 1, previous + [top]))
representations[rep] = []
else:
if top == endWord:
result.append(previous + [top])
return result
这是Dijkastra算法的解决方案。第一步是建立图形。第二步就是简单地找到算法从头到尾的路径
import heapq
beginWord = "hit"
endWord = "cog"
wordList = ["hot","dot","dog","lot","log","cog"]
class Node:
def __init__(self, word):
self.word = word
self.children = []
self.visited = False
self.last = None
def __str__(self):
s = ""
s += self.word + "\n"
s += ",".join([c.word for c in self.children]) + "\n"
s += str(self.visited) + "\n"
return s
def buildGraph(begin, end, wordList):
all_words = wordList + [begin, end]
all_words = list(dict.fromkeys(all_words))
d = { w : Node(w) for w in all_words }
for i, w in enumerate(all_words):
for w2 in (all_words[i+1:]):
if canHop(w, w2):
d[w].children.append(d[w2])
d[w2].children.append(d[w])
return d
def canHop(w, w2):
return len(list(filter(lambda x: x == False, [c == w2[i] for i, c in enumerate(w)] ))) == 1
graph = buildGraph(beginWord, endWord, wordList)
s = graph[beginWord]
e = graph[endWord]
def findLadders(s, e, graph):
scores = []
heapq.heapify(scores)
s.visited = True
paths = [s]
heapq.heappush(scores, (0, s.word))
flag = False
while len(scores) > 0:
d, w = heapq.heappop(scores)
n = graph[w]
for c in n.children:
if c.visited:
continue
c.last = n
if c == e:
flag = True
break
c.visited = True
heapq.heappush(scores, (d+1, c.word))
if flag:
break
result = []
last = e
while last is not None:
result.append(last.word)
last = last.last
return result
print(findLadders(s,e,graph))