最长公共子序列问题python

以下是一个Python实现的最长公共子序列（LCS）问题的解决方案：

def lcs(s1, s2):
    m = len(s1)
    n = len(s2)
    # 创建一个m+1行n+1列的空矩阵
    L = [[None]*(n+1) for i in range(m+1)]
    # 填充矩阵
    for i in range(m+1):
        for j in range(n+1):
            if i == 0 or j == 0:
                L[i][j] = 0
            elif s1[i-1] == s2[j-1]:
                L[i][j] = L[i-1][j-1] + 1
            else:
                L[i][j] = max(L[i-1][j], L[i][j-1])
    # 获取LCS
    index = L[m][n]
    lcs = [""] * (index+1)
    lcs[index] = ""
    i = m
    j = n
    while i > 0 and j > 0:
        if s1[i-1] == s2[j-1]:
            lcs[index-1] = s1[i-1]
            i -= 1
            j -= 1
            index -= 1
        elif L[i-1][j] > L[i][j-1]:
            i -= 1
        else:
            j -= 1
    return "".join(lcs)

该函数接受两个字符串作为输入，返回它们的最长公共子序列。它使用一个二维矩阵来存储问题的所有子问题的解，并使用该矩阵来计算最长公共子序列。 它的时间复杂度是O(mn)，其中m和n分别是两个字符串的长度。