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

from re import X

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
		#如果2个串，有一个为空那么输出为空
        if not s1 or not s2:
            return "-1"
		  
        m = len(s1)
        n = len(s2)
        dp = [[0 for i in range(n + 1)] for i in range(m + 1)]

        # 构建一个parent数组，存放i，j的上一层来在哪个元素
        parent = [[[] for i in range(n + 1)] for i in range(m + 1)]

        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
                    parent[i][j] = [i - 1, j - 1]

                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                    if dp[i - 1][j] > dp[i][j - 1]:
                        parent[i][j] = [i - 1, j]
                    else:
                        parent[i][j] = [i, j - 1]
						

		#因为parent数组中没有存放最后一个元素的关系，那么需要提前比较一下，最后一个元素	
        x = parent[m][n]
        if s1[-1]==s2[-1]:
            res=s1[-1]
        else:
            res = ""
		
        L = []
        while x:
    #比较s1中i-1的元素的值和，s2中j-1的值，如果不相等，说明还需要继续查找，如果相等，将该值加入到res
            i, j = x[0], x[1]
            x = parent[i][j]
            if s1[i - 1] == s2[j - 1]:
                res = s1[i - 1] + res
                L.append(x)
	   #如果最后res为空，返回-1
        if not res:
            return "-1"
        return res