题解 | 最长公共子序列(二)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        n=len(s1)
        m=len(s2)
        #定义dp[i][j]  表示 s1[0 ,i-1] s[0,j-1] 的最长
        dp=[[0] * (m+1) for _  in range(n+1)]
        for i in range(1,n+1):
            for  j in range(1,m+1):
                if s1[i-1]==s2[j-1]:
                    dp[i][j]=dp[i-1][j-1]+1
                else:
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])
        if dp[n][m]==0:  # 没有公共子序列
            return "-1"
        #print(dp)
        i,j=n,m
        lcs=[]
        while i>0 and j>0:
            if s1[i-1]==s2[j-1]:
                lcs.append(s1[i-1])
                i-=1
                j-=1
            elif  dp[i-1][j]>dp[i][j-1]:
                i-=1
            else:
                j-=1
        print(dp)
        
        return "".join(lcs[::-1])