题解 | #最长公共子序列#

def cal(str1: str, str2: str):
    '''
    str1:第一个字符串
    str2:第二个字符串
    return:最长公共子序列
    '''
    '''
    dp数组，第i行，第j列：str1的前i个字符和str2的前j个字符的最长公共子序列
    '''
    dp0 = [''] * len(str2)
    dp = []
    for i in range(len(str1)):
        dp.append(dp0.copy())
    '''
    边界条件：第一行，j列：str1的第一个字符和str2的前j个字符的最长公共子序列
    '''
    for j in range(len(str2)):
        if str1[0] in str2[:j + 1]:
            dp[0][j] = str1[0]

    '''
    边界条件：第一列：i行，str1的前i个字符和str2的第一个字符的最长公共子序列
    '''
    for i in range(len(str1)):
        if str2[0] in str1[:i + 1]:
            dp[i][0] = str2[0]
    '''
    状态转移方程：
        如果str2的第j个字符等于str1的第i个字符，则dp[i][j]=dp[i-1][j-1]+str[i]
        否则，dp[i][j]=(dp[i-1][j],d[i][j-1],dp[i-1][j-1])中最长的一个
    '''
    for i in range(1, len(str1)):
        for j in range(1, len(str2)):
            if str1[i] == str2[j]:
                result= dp[i - 1][j-1] + str2[j]

            else:
                tem1 = dp[i - 1][j]
                tem2 = dp[i][j - 1]
                tem3 = dp[i - 1][j - 1]
                if (len(tem1) >= len(tem2) and len(tem1) >= len(tem3)):
                    result = dp[i - 1][j]
                elif (len(tem2) >= len(tem1) and len(tem2) >= len(tem3)):
                    result= tem2
                else:
                    result = tem3
            dp[i][j]=result
    output=dp[len(str1) - 1][len(str2) - 1]
    if len(output)<1:
        print(-1)
    else:
        print(output)


str1 = input()
str2 = input()
cal(str1, str2)