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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
import copy
class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        # write code here
        n1 = len(s1)
        n2 = len(s2)
        if n1 == 0 or n2 == 0:
            return '-1'
            
        i = 0

        # dp[i][j]表示前i的s1和前j的s2之间的最长公共子序列
        # dp[i+1][j+1]
        # 如果s1[i] == s2[j], dp[i+1][j+1] = dp[i][j] + 1
        # 如果s1[i] != s2[j], dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1])

        dp = [['' for _ in range(n2 + 1)] for _ in range(n1 + 1)]

        for i in range(n1):
            for j in range(n2):
                if i == 0 and j == 0:
                    dp[i][j] = s1[i] if s1[i] == s2[j] else ''

                if s1[i] == s2[j]:
                    dp[i][j] = dp[i-1][j-1] + s1[i]
                else:
                    if len(dp[i - 1][j]) > len(dp[i][j-1]):
                        dp[i][j] = dp[i - 1][j]
                    else:
                        dp[i][j] = dp[i][j-1]
        rst = dp[-2][-2]
        if rst == '':
            return '-1'
        else:
            return rst