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

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        if len(s1)==0 or len(s2)==0:
            return "-1"
        dp = [[[-1,-1,-1] for j in range(len(s2))] for i in range(len(s1))]
        dpstr = [['' for j in range(len(s2))] for i in range(len(s1))]
        if s1[0]==s2[0]:
            dp[0][0]=[0,0,1]
            dpstr[0][0] = s1[0]
        else:
            dp[0][0] = [-1,-1,-1]
        
        for i in range(len(s1)):
            for j in range(len(s2)):
                a1this = [-1,-1,-1]
                a2this = [-1,-1,-1]
                a1str = ''
                a2str = ''

                if i>0:
                    a1 = dp[i-1][j]
                    if a1[2]!=-1:
                        if s1[i] in s2[a1[1]+1:j+1]:
                            ind = a1[1]+s2[a1[1]+1:j+1].index(s1[i])+1
                            a1this = [i,ind,a1[2]+1]
                            a1str = dpstr[i-1][j]+s1[i]
                        else:
                            a1this = a1
                            a1str = dpstr[i-1][j]
                    else:
                        if s1[i] in s2[:j+1]:
                            ind = s2[:j+1].index(s1[i])
                            a1this = [i,ind,1]
                            a1str = s1[i]
                if j>0:
                    a2 = dp[i][j-1]
                    if a2[2]!=-1:
                        if s2[j] in s1[a2[0]+1:i+1]:
                            ind = a2[0]+s1[a2[0]+1:i+1].index(s2[j])+1
                            a2this = [ind,j,a2[2]+1]
                            a2str = dpstr[i][j-1]+s2[j]
                        else:
                            a2this = a2
                            a2str = dpstr[i][j-1]
                    else:
                        if s2[j] in s1[:i+1]:
                            ind = s1[:i+1].index(s2[j])
                            a2this = [ind,j,1]
                            a2str = s2[j]

                if a1this[2]>0 and a1this[2]>a2this[2]:
                    dp[i][j]=a1this
                    dpstr[i][j] = a1str
                elif a2this[2]>a1this[2] and a2this[2]>0:
                    dp[i][j]=a2this
                    dpstr[i][j] = a2str
                elif a2this[2]==a1this[2] and a2this[2]>0:
                    dp[i][j]=a1this
                    dpstr[i][j] = a1str
                else:
                    pass
        
        if dp[-1][-1][2]!=-1:
            return dpstr[-1][-1]
        else:
            return '-1'