递归搜索词典中的句子（片段）（python）

Question

如果可以从给定的段列表 seglist 生成给定的序列 x，则该程序应该 return 为真。在找到一种可能的解决方案后，它应该停止。

我尝试替换和重新定位 return 命令，但总是出现不同的问题。

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            return valid_sequence(x[len(i):], seglist)
    return False

这 return 是序列 'abc' 和 seglist ['a', 'ab', 'bc', 'c']、['a', 'b', 'c'] 和 ['ab', 'bc'] 的正确布尔值，但不适用于 seglist [=18] =] 因为显然它正在通过 'a' 变体，但不会成功并在应该通过 'ab' 之前停止。

我运行通过 pythontutor 了解了一些问题，但我无法确定如何解决它们。

如何编写它，以便它在 'a' 的不成功路径后继续段 'ab'？也许我还遗漏了其他东西，因为我无法理解这个递归。

这种方法是否可行，还是我必须采取完全不同的方法？

Answer 1

正如您正确识别的那样，您的代码的问题是您的程序 return 在每个位置都用尽所有可能的字符串选择之前过早地为 False。

特别是，当运行以下行时 return 为 False：

return valid_sequence(x[len(i):], seglist)

如果您考虑一下，该程序应该永远无法在该位置 return False，因为它可能尚未完成对 seglist 中所有字符串的迭代。但是，如果找到了完成序列的字符串选择，您确实希望 return 为真。

幸运的是，只需稍作修改即可解决此问题：在 returning 之前检查值 returned 是否为 True。我在下面包含了修改后的代码。

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            if valid_sequence(x[len(i):], seglist):
                return True
    return False

Answer 2

你在这方面非常接近。主要问题是你不应该在递归步骤中立即 return 。请注意，在调用它的第一个循环之后，它将 return False 。因此，整个函数也将 return False。

说，只有当结果为真时，你才应该return：

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            if valid_sequence(x[len(i):], seglist):
                return True
    return False

这将解决您提到的问题，但还有一个问题需要解决。如果 x = 'abc' 和 seglist = ['ab', 'b', 'c'] 函数将正确 return True。但它也会 return True for x = 'abbc', x = 'abbbc' 等等。发生这种情况是因为 'b' 被无限期使用。我想这是一种不受欢迎的行为。为了克服这个问题，我们为新调用创建了列表的副本并删除了使用的元素：

import copy

def valid_sequence(x, seglist): 
    if x in seglist:
        return True

    for i in seglist:
        if x.startswith(i):
            newlist = copy.deepcopy(seglist)
            newlist.remove(i)
            
            if valid_sequence(x[len(i):], newlist):
                return True
    return False

递归搜索词典中的句子（片段）（python）

Recursivey searching (segments of) a sentence in a lexicon (python)

python

recursion

startswith