题解 | #最长公共子串#

首先是用dp来解这道题，dp解的话关键就在于找到状态转移方程，这个题的状态转移方程和找最长公共子序列不同，因为子串必须要是连续的串。 LCS[i][j]为以s1[i]和s2[j]为结尾最长子串，因此就容易得到状态转移方程了,if s1[i]!=s2[j]的话，那么LCS[i][j]=''，而如果s1[i]==s2[j]的话，那么LCS[i][j]=LCS[i-1][j-1]+s1[i]。有了状态转移方程之后就很好写代码了，但是用python写dp的话会报时间复杂度不过关，应该是python语言导致的，复杂度肯定是满足要求的。

但是从状态转移方程就可以看出来这道题用dp做确实有点浪费，可以用划窗来做，new两个指针p1和p2，两个指针中间就构成了一个划窗，然后不断移动划窗找到最大子串。当s1[p1:p2]在s2中，p2右移一个，不在的话p1右移一个，不过要注意p1不可以超过p2，因此p1=p2了之后，就p2右移即可。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# longest common subsequence
# @param s1 string字符串 the string
# @param s2 string字符串 the string
# @return string字符串
#
class Solution:
    def LCS1(self , s1: str, s2: str) -> str:
        # dp解题时间复杂度超标，应该是用python写导致的
        LCS = [['']*len(s2) for i in range(len(s1))]
        maxlcs = ''
        # 初始化边界条件，第0行和第0列
        for j in range(len(s2)):
            if s1[0] == s2[j]:
                LCS[0][j]=s1[0]
                if len(LCS[0][j]) > len(maxlcs):
                    maxlcs = LCS[0][j]
            else:
                pass
        for i in range(len(s1)):
            if s1[i]==s2[0]:
                LCS[i][0] = s2[0]
                if len(LCS[i][0]) > len(maxlcs):
                    maxlcs = LCS[i][0]
            else:
                pass
        # 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]
                    if len(LCS[i][j]) > len(maxlcs):
                        maxlcs = LCS[i][j]
                else:
                    pass
        return maxlcs

    def LCS(self,s1,s2):
        # 划窗法
        res = ''  # 保存最长子串
        p1 = 0 ; p2 = 0
        while p2<=len(s1):
            if s1[p1:p2] in s2:
                if len(s1[p1:p2]) > len(res):
                    res = s1[p1:p2]
                p2+=1
            else:
                if p1<p2:
                    p1+=1
                else:
                    p2+=1
        return res

s1 = '1A23'
s2 = '123'
print(Solution().LCS(s1,s2))