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

import enum
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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, m = len(s1), len(s2)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s1):
            for j, y in enumerate(s2):
                if x == y:
                    f[i + 1][j + 1] = f[i][j] + 1
                else:
                    f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j])
        if f[-1][-1] == 0:
            return str(-1)
        ans, i, j = '', n, m
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:   # 找到了
                ans += s1[i - 1]
                i -= 1
                j -= 1
            else:
                if f[i][j - 1] >= f[i - 1][j]: # [i, j-1] 转移过来的
                    j -= 1
                else:
                    i -= 1
        return ans[::-1]