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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        n1,n2= len(s1),len(s2)
        dp =[[0]*(n2+1) for _ in range(n1+1)]
        for i in range(1,n1+1):
            for j in range(1,n2+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])
        ans =''
        i,j =n1,n2
        while i>=1 and j>=1:
            if s1[i-1] == s2[j-1]:
                ans = s1[i-1]+ans
                i-=1
                j-=1
            else:
                if dp[i][j-1]>dp[i-1][j]:
                    j-=1
                else:
                    i-=1
        return ans if ans !='' else '-1'