Python字符串LCS

Question

我打算实现一个LCS版本，它执行以下I/O操作：

输入: 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)

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的长度。要检索(其中一个可能的) LCSes，您需要从右下角到左上角执行额外的“回溯”。

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

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