使用 python 递归的单词字典搜索

Question

>我必须做一个函数：

    def allPaths(input,destination,num):

它输入是字典中的一个单词，目标也是字典中的一个单词。 num 是从输入到目标必须获得的递归调用数。

    def oneLetterDiff(word):

这将返回字典中任何字符串索引中一个字母偏差的所有单词（列表）。它已经写好并工作了。

如何让所有路径递归搜索所有 OneLetterDiff（及其返回的列表）以 num 指定的次数？如果找到目的地，它必须返回到达目的地所花费的单词（也称为路径）。

当前代码：

    def wordPath(word, dest, times):
        path = []
        offOne = oneLetterDiff(word)

        if times > 0:
            if word == dest:
                path.append(word)
                return path
    return path

谢谢！

劳 埃 德

Answer 1

首先，你必须写出你的基本情况。您已经知道如何执行此操作：

def wordPath(word, dest, times):
    if times == 0:
        return []
    if word == dest:
        return [word]

而且您还知道要进行哪些递归调用：

    offones = oneLetterDiff(word)
    for offone in offones:
        result = wordPath(offone, dest, times-1)
        ??? something with each result ???
    ??? something if you run out of results to try ???

所以，你必须弄清楚你想用result做什么。答案取决于你得到的结果。它将是一条路径——一个单词列表。但你知道，空列表意味着失败，一个单词列表意味着路径的尽头;你只需要弄清楚如何从那里构建。

如果它返回一个空列表，则意味着没有通过offone的路径。但这并不意味着没有通过word的路径;只有当你到达列表的末尾，并且它们都返回[] 时，您才会知道。因此，在这种情况下，请继续下一个循环。

如果它返回[dest]（当然，这也与[offone]相同），这意味着从word到dest的路径只是[word, dest]。所以，这就是你返回的内容。

如果它返回其他内容，例如 [offone, <some other word>, dest] ，那么您就知道它成功了。那么，在这种情况下，从word到dest的路径是什么？这就是你返回的。

如果你弄清楚了，你就差不多完成了。