Python字符串LCS

Question

我想实现一个版本LCS的，做了以下I/O：

输入：superLCS（ '猫'， '汽车'）

输出： 'CA＃' ，'ca＃']

目前，我的程序适用于此，但如果字母不合适，它不起作用。例如，如果输入是：superLCS（'art'，'cad'），则输出['###'，'###']。应该输出[ '一##'， '＃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) 

Answer 1

你的问题是算法。 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。

这是所有解释和证明很好on Wikipedia。