python - 如何更正此 python dfs 搜索？

Question

我正在编写实现 dfs 的 python 代码，但我无法使其正常工作。这是一个愚蠢的例子，使用 dfs 查看 word 是否可以由 lst 组成:

def dfs(word, gen):
    print(gen)
    if len(gen) <= len(word):
        if gen == word:
            return True
        lst = ["a","b"]
        for i in lst:
            dfs(word, gen+i)
    return False

print(dfs("ba",""))

这里我的 lst 是 ["a", "b"] 并且它显然可以形成 "ba"。但是它返回 False。我每次通过 print(gen) 得到它形成的单词的输出:

a
aa
aaa
aab
ab
aba
abb
b
ba
bb
bba
bbb

而且我可以在结果中看到 ba，那么程序是否应该在遇到 ba 时停止递归并返回 True？我的代码有什么问题？

Answer 1

问题出在这里:

for i in lst:
    dfs(word, gen+i)

一旦找到单词，它将返回 True，但调用者将忽略返回的 True 值，您将最终生成所有单词并返回 False 在任何情况下。
您只需添加一个检查，以便在找到匹配项时返回 True。

for i in lst:
    if dfs(word, gen+i):
        return True

此外，移动一些行，您的函数可以用更简洁的方式编写为:

def dfs(word, gen):
    if len(gen) > len(word):
        return False
    elif gen == word:
        return True
    else:
        return any(dfs(word, gen+i) for i in ("a","b","c"))