这是一道在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)]
