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

关键在于找到状态转移方程。令LCS[i][j]代表s1[0:i+1],s2[0,j+1]的最长公共子串，则状态转移方程为：

$L C S [i] [j] = L C S [i - 1] [j - 1] + s 1 [i], i f s 1 [i] = s 2 [j]$

$LCS[i][j]=maxlen\{LCS[i-1][j],LCS[i][j-1]\},if s1[i]!=s2[j]$

也就是说当s1[i]=s2[j]时，此时的最长公共子串就是LCS[i-1][j-1]在后面加上相同的那个字符串；当s1[i]！=s2[j]时，那么s1[i]和s2[j]不可能同时成为最长公共子串的最后一位，因此有三种可能，要么s1[i]是最长子串最后一位，要么s2[j]是最长子串最后一位，要么都不是，此时最长子串也就是LCS[i-1][j]和LCS[i][j-1]中较长的那一个了。

有了状态转移方程后，代码实现是比较简单的，new一个二维数组，然后先初始化边界条件，第0行和第0列，然后按照行去补全矩阵，返回最后一个元素即可了。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 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
        # 初始化LCS矩阵
        LCS = [[''] * (len(s2)) for i in range(len(s1))]
        # 初始化矩阵第一行和第一列,矩阵第0行第0列就是默认值''即可不需要修改
        for j in range(len(LCS[0])):
            if j==0 :
                if s1[0]==s2[0]:
                    LCS[0][0]=s1[0]
                else:
                    pass
            else:
                if s1[0] == s2[j]:
                    LCS[0][j]=s1[0]
                else:
                    LCS[0][j]=LCS[0][j-1]
        for i in range(len(LCS)):
            if i == 0:
                pass
            else:
                if s1[i]==s2[0]:
                    LCS[i][0] = s2[0]
                else:
                    LCS[i][0] = LCS[i-1][0]
        # print(LCS)
        # 基于状态转移方程补全矩阵,按照行来补
        for i in range(1,len(s1)):
            for j in range(1,len(s2)):
                if s1[i] == s2[j]:
                    LCS[i][j] = LCS[i-1][j-1]+s1[i]
                else:
                    tmp1 = LCS[i-1][j] ; tmp2 = LCS[i][j-1]
                    if len(tmp1)>len(tmp2):
                        LCS[i][j] = tmp1
                    else:
                        LCS[i][j] = tmp2
        if LCS[-1][-1]=='':
            return -1
        else:
            return LCS[-1][-1]


s1 = 'abcd'
s2 = 'abc'
print(Solution().LCS(s1,s2))