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

最长公共子序列，动态规划，时间O(mn)，空间O(min(m,n)*k)，k为最长公共子序列长度

类似于：https://www.nowcoder.com/discuss/388075528203378688
只是该问题的状态表示最长公共子序列本身而非长度。

class Solution:
    def LCS(self , s1: str, s2: str) -> str:
        if not s1 or not s2: return -1
        if len(s1) > len(s2):
            s1, s2 = s2, s1          # 让s1表示短串
        m, n = len(s1), len(s2)
        dp = ['']*(m+1)              # 根据短串的长度构造dp
        for i in range(n):
            pre_dp = dp[0]           # 初始的[i-1][j-1]位置的dp，为dp[0]，一直为空，便于算边缘位置
            for j in range(m):
                if s1[j] == s2[i]:     # 相等        
                    tmp = dp[j+1]      # 记录下一个[i-1][j-1]位置的dp备用，为之前的dp[j+1]
                    dp[j+1] = pre_dp + s1[j] # 状态转移
                    pre_dp = tmp
                else:
                    pre_dp = dp[j+1]   # 记录下一个[i-1][j-1]位置的dp备用，为之前的dp[j+1]
                    dp[j+1] = dp[j+1] if len(dp[j+1]) > len(dp[j]) else dp[j] # 状态转移
        if dp[-1]:  # 可能为''
            return dp[-1]
        else: 
            return -1