0

我想实现一个执行以下 I/O 的 LCS 版本：

输入：superLCS('cat','car')

输出：['ca#','ca#']

目前，我的程序适用于此，但如果字母不合适，它就不起作用。

例如，如果输入是：superLCS('art','cad')，则输出 ['###','###']。它应该输出 ['a##','#a#']

代码：

def superLCS(s1,s2):
    return helper(s1,s2,'','')

def helper(s1,s2,res1,res2):  #s1 is string 1, s2 is string 2, res1 is result1, res2 is result2
    if s1 == '' or s2 == '': #if either string is empty return the result
        return [res1,res2]
    if s1[0] == s2[0]: #if they are equal, put their string in the list
        res1 += s1[0]
        res2 += s1[0]
        return helper(s1[1:],s2[1:],res1,res2)
    else:  #if they arent, add a # to the list
        res2 += '#'
        res1 += '#'
        return helper(s1[1:],s2[1:],res1,res2)
4

1 回答 1

0

你的问题是算法问题。LCS 是一种经典的动态规划算法，您必须在其中填充一个维度的“矩阵” len(s1) x len(s2)，每个值M[i,j]取决于其上方单元格的值，M[i-1,j]在其左侧M[i,j-1]，以及对角线上方的左侧M[i-1][j-1]，这是只是为了获得LCS的长度。要检索（其中一个潜在的）LCS，您需要从右下角到左上角进行额外的“回溯”。

由于您不这样做，因此您正在对子序列空间进行更简单、更窄的搜索，因此在您的第二个示例中找不到正确的 LCS。

这一切都在 Wikipedia 上得到了很好的解释和演示。

于 2012-09-22T16:15:18.797 回答