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

> - `dp[i][j]`表示i第一个字符串前`i`个和第二个字符串前`j`个字符最长的子序列长度.

> - `dp[i][j]=[[0]*m for _ in range(n)]` 其中m=len(s1), n=len(s2).

> - 如果`s1[i]==s2[j]`,则 `dp[i][j]=dp[i-1][j-1]+1`否则`dp[i][j]=max(dp[i][j-1],dp[i-1][j])`

> - 需要注意的是,结果求的是子序列,而不是子序列的长度,因此需要另外维护一个`dir[m][n]`来记录每个状态是从何处转移过来的,可以用1,2,3来代替三个方向.

> - 最后根据dir最后一项反推出最长的那个公共子序列.

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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:
        m = len(s1)
        n = len(s2)
        dp = [[0] * (n+1) for _ in range(m+1)]
        dir = [[0] * n for _ in range(m)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if s1[i-1] == s2[j-1]:
                    dp[i][j] = dp[i-1][j-1] + 1
                    dir[i-1][j-1] = 2
                else:
                    if dp[i][j-1] > dp[i-1][j]:
                        dp[i][j] = dp[i][j-1]
                        dir[i-1][j-1] = 1
                    else:
                        dp[i][j] = dp[i-1][j]
                        dir[i-1][j-1] = 3
        # 开始根据dir还原选择的字符,如果输入的是s1,则使用i的位置,s2则用j
        ans = []
        def restore(i,j,s,dir,ans):
            if i < 0 or j < 0:
                return
            if dir[i][j] == 2:
                restore(i-1,j-1,s,dir,ans)
                ans.append(s[i])
            else:
                if dir[i][j] == 1:
                    restore(i,j-1,s,dir,ans)
                else:
                    restore(i-1,j,s,dir,ans)

        restore(m-1, n-1, s1, dir, ans)
        return ''.join(ans) if dp[-1][-1] else -1