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

#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS(self , s1 , s2 ):
        # write code here
        if not s1 or not s2:
            return "-1"
        m,n = len(s1),len(s2)
        mark = [[0]*(n+1) for i in range(m+1)]
        for i in range(m):
            for j in range(n):
                if s1[i]==s2[j]:
                    mark[i+1][j+1] = 1 + mark[i][j]
                else:
                    mark[i+1][j+1] = max(mark[i+1][j],mark[i][j+1])
        if not mark[m][n]:
            return "-1"
        return self.search(s1,s2,mark)
    
    def search(self,s1,s2,mark):
        m,n = len(s1),len(s2)
        res = ""
        while m>0 and n>0:
            if mark[m][n] == mark[m-1][n-1]:
                m -= 1
                n -= 1
                continue
            if mark[m][n] == mark[m-1][n]:
                m -= 1
                continue
            if mark[m][n] == mark[m][n-1]:
                n -= 1
                continue
            if mark[m][n] == mark[m-1][n-1]+1:
                res += s1[m-1]
                m -=1 
                n -= 1
        return res[::-1]