Python 最长公共子序列 LCS算法

def lcs(s1, s2):
    matrix = [[[] for x in range(len(s2))] for x in range(len(s1))]
    for i in range(len(s1)):
        for j in range(len(s2)):
            if s1[i] == s2[j]:
                if i == 0 or j == 0:
                    matrix[i][j].append(s1[i])
                else:
                    matrix[i][j].extend(matrix[i-1][j-1])
                    matrix[i][j].append(s1[i])
            else:
                matrix[i][j] = max(matrix[i-1][j], matrix[i][j-1], key=len)

    return matrix[-1][-1]

if __name__ == '__main__':
    s1 = "abcd"
    s2 = "bd"

    print(lcs(s1, s2))

>>['b', 'd']