LCS（最大公共子序列）问题的Python解法

这是一道在codewars上看到的rank4的题目 LCS算是经典的算法题 时间复杂度为O(n^2) 由于解法巧妙 特此记录

子序列

一个字符串的子序列和子串不同，他不必是连续的，但是依旧得按照顺序

例如：

"abc"="a","b","c","ab","ac","bc","abc"

最大子序列的例子

lcs( "abcdef" , "abc" ) => returns "abc"
lcs( "abcdef" , "acf" ) => returns "acf"
lcs( "132535365" , "123456789" ) => returns "12356"

有如下前提条件

• 两个参数均是字符串
• 返回值也是字符串
• 如果无LCS 返回空串
• 所有测试用例只包含一个最大公共子序列 不用担心两个以上的解的问题

wiki上关于LCS的资料如下

Longest common subsequence problem

主要关注解决这个问题的两个重要属性

• 如果两个字符串拥有相同的末位字符，则他们的LCS(xn, ym)等于LCS(xn-1, ym-1) ^ xn
• 如果两个字符串末位字符不同，则他们的LCS(xn, ym)等于longest(LCS(xn-1,ym), LCS(xn, ym-1))

具体的原因可以看wiki中的详细解释

以下是解法（不使用递归）

def lcs(x, y):
    matrix = [''] * (len(x) + 1)
    for index_x in range(len(matrix)):
        matrix[index_x] = [''] * (len(y) + 1)

    for index_x in range(1,len(x) + 1):
        for index_y in range(1,len(y) + 1):
            if x[index_x - 1] == y[index_y - 1]:#这里利用属性一
                matrix[index_x][index_y] = matrix[index_x - 1][index_y - 1] + x[index_x - 1]
            elif len(matrix[index_x][index_y - 1]) > len(matrix[index_x -1][index_y]):#这里和下面利用属性二
                matrix[index_x][index_y] = matrix[index_x][index_y - 1]
            else:
                matrix[index_x][index_y] = matrix[index_x - 1][index_y]
    
    return matrix[len(x)][len(y)]