My Find Ladders解决方案无法更新代表当前节点路径的列表

问题描述 投票:0回答:1

这是问题描述:

给出两个单词(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
python algorithm graph breadth-first-search
1个回答
0
投票

这是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))
© www.soinside.com 2019 - 2024. All rights reserved.