這是一道在codewars上看到的rank4的題目 LCS算是經(jīng)典的算法題 時間復雜度為O(n^2) 由于解法巧妙 特此記錄

子序列

一個字符串的子序列和子串不同，他不必是連續(xù)的，但是依舊得按照順序

例如：

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

最大子序列的例子

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

有如下前提條件

• 兩個參數(shù)均是字符串
• 返回值也是字符串
• 如果無LCS 返回空串
• 所有測試用例只包含一個最大公共子序列 不用擔心兩個以上的解的問題

wiki上關(guān)于LCS的資料如下

Longest common subsequence problem

主要關(guān)注解決這個問題的兩個重要屬性

• 如果兩個字符串擁有相同的末位字符，則他們的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)]