1

我正在尝试在 python 中使用递归来实现这个函数，但我有一个错误。我不明白是什么错误，你能帮帮我吗？

编码：

def LongestCommonSubsequence(X,Y,tailX,tailY):
    if tailX == tailY and tailX!='' and (X=='' or Y==''):
            return len(tailX)
    elif X=='' or Y=='':
            return 0
    else:

        return max( LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX+X[0],tailY),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY+Y[0]),
                    LongestCommonSubsequence(X[1:],Y[1:],tailX,tailY)) 

X=raw_input() 
Y=raw_input() 
print LongestCommonSubsequence(X,Y,'','')

输入：

abccdabab 
bacdbeb

预期输出：5
我得到什么：4

4

1 回答 1

2

您似乎在这里尝试针对常见的尾字符串进行优化；如果两个字符串都以相同的尾部结尾，您确实可以跳过一些递归步骤。

但你实际上并不是在建造尾巴，而是在建造头部，开始时的角色。

llcs这是一个没有优化的工作递归：

def llcs(xstr, ystr):
    if not xstr or not ystr:
        return 0
    x, xtail, y, ytail = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))

xstr这通过比较从一个或ystr而不是两个的开头删除字符的长度来找到最大最长公共子字符串长度。

X您的代码永远不会与调用配对Y[1:]或X[1:]与调用配对，因此您永远不会Y在或max()中找到该特定起始字符的 LCS 。XY

然后，您可以通过查看xtail和ytail（实际尾部）来尝试优化并尽早退出：

def llcs(xstr, ystr):
    if not xstr or not ystr:
        return 0
    x, xtail, y, ytail = xstr[0], xstr[1:], ystr[0], ystr[1:]
    if x == y:
        if xtail == ytail:
            # if the tails match, bail out early
            return 1 + len(xtail)
        return 1 + llcs(xtail, ytail)
    return max(llcs(xstr, ytail), llcs(xtail, ystr))
于 2015-02-06T15:34:31.953 回答