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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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:
        c = [[0 for _ in range(len(s1) + 1)] for _ in range(len(s2) + 1)]
        # 取元素时候外面的在前，比如c[i][j]
        # 这里增广一圈，方便计算
        for i in range(len(s2)):
            for j in range(len(s1)):
                if s2[i] == s1[j]:
                    c[i+1][j+1] = c[i][j] + 1
                else:
                    c[i+1][j+1] = max(c[i][j+1],c[i+1][j])
        if c[-1][-1] == 0:
            return '-1'
        i = len(s2) - 1
        j = len(s1) - 1
        s = ''
        while True:
            if c[i+1][j+1] == c[i][j+1]:
                i -= 1
            elif c[i+1][j+1] == c[i+1][j]:
                j -= 1
            else:
                s = s2[i] + s
                i -= 1
                j -= 1            
            if c[i+1][j+1] == 0:
                break
        return s