20211202完全对称日，我们一起来温习一下

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:643780a3-ac23-40ab-bdf5-96317abfaae5

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:aa4058cb-982c-4d3c-9637-f0dfd8805107

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:02279e1a-166a-43c3-8e10-c75a238b46cc

Tips：回文串就是正反读都是一样的字符串，比如”上海自来水来自海上”。

问题描述

给你一个字符串 s，找到s中最长的回文子串。
示例:
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <="1000" s 仅由数字和英文字母（大写和 或小写）组成 code></=>

分析问题

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e878ff4f-e7ea-4357-90ed-a2345c126d21

def isPalindromic(ss):
    n=len(ss)
    for i in range(int(n/2)):
        if(ss[i]!=ss[n-i-1]):
            return False
    return True

def longestPalindrome(s):
    ans=""
    maxlen=0
    n=len(s)
    #求出所有子串
    for i in range(n):
        for j in range(i+1,n):
            ss=s[i:j]
            #判断子串是否是“回文”
            if(isPalindromic(ss)):
                #拿出最长的
                if(len(ss)>maxlen):
                    ans=ss
                    maxlen=len(ss)
    return ans

print(longestPalindrome("cbbd"))

这个算法的实现复杂度是O(n^3)，空间复杂度是O(1)。那我们有什么优化方式来降低时间复杂度吗？

优化

既然你正反读是一样的，我们把原字符串翻转生成一个新的字符串，然后拿新的字符串和原字符串求最长公共子串不就可以了吗？那我们如何求两个字符串的最长公共子串呢？既然要找公共子串，那不就是求出两个字符串的所有子串，然后比较他们是否相同，找出最长的相同的子串。显而易见，这个算法的时间复杂度也是O(n^3)，这不和上面那个算法复杂度一样吗？也没优化上啊。

def longestCommonSubstring(s1,s2):
    n1=len(s1)
    n2=len(s2)
    maxlen=0
    ans=""
    for i in range(n1):
        for j in range(n2):
            length=0
            m=i
            n=j
            while m<n1 and n<n2: if s1[m]!="s2[n]:" break m="m+1" n="n+1" length="length+1"> maxlen:
                maxlen=length
                ans=s1[i:i+maxlen]
    return ans
</n1>

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:c6c03f88-bcef-44a4-abc1-8ffeb7d6d17f

有了上面的这个解答，面试官肯定是不满意嘛。要想拿到offer，我们还得加把劲。

我们来看上面的解答有哪些问题呢？我们可以知道在进行子串比较的过程中，多了很多重复的比较。也就是代码里的while循环部分。比如我们在比较以i和j分别为起点的子串时，有可能会进行 i+1和 j+1以及 i+2和 j+2位置的字符的比较。而在比较以 i+1 和j+1分别为起始点字符串时，这些字符又会被比较一次了。这就说明了该问题有”重叠子问题”的特征，那我们是不是可以用动态规划来解决呢？

我们假设两个字符串分别为s和t，s[i]和t[j]分别表示第i和第j个字符。我们用a[i] [j]表示以s[i]和t[j]为结尾的相同子串的最大长度。那我们就可以很容易推导出a[i+1] [j+1]之间的关系，这两者之间就差a[i+1]和t[j+1]这一对字符，如果a[i+1]和t[j+1]相等，那么a[i+1] [j+1]=a[i] [j] +1，如果不相等，则a[i+1] [j+1]=0。当i=0或者j=0时，对应字符相等的话a[i] [j]=1，不相等的话，则为0。下面，我们来看一下代码如何实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[[0 for _ in range(n)] for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[i][j]=1
                else:
                    a[i][j]=a[i-1][j-1]+1

            if a[i][j] > maxlen:
                maxlen=a[i][j]
                #以i为结尾的子串
                maxend=i

    return s[maxend-maxlen+1:maxend+1]

我们来看下面这个例子S1=”abcedcba”，S2=”abcdecba”。最长的公共子串是”abc”和”cba”，但很明显这不是回文子串。所以，我们在求出最长公共子串后，还需要判断一下该子串倒置前后的下标是否相匹配。比如S1=”daba”，S2=”abad”。S2中aba的下标是0，1，2，倒置前是3，2，1，和S1中的aba的下标符合，所以aba是最长回文子串。其实，我们不需要每个字符都判断，我们只需要判断末尾字符就可以了。

如图所示，我们来看最长公共子串”aba”在翻转前后末尾字符”a”对应的下标分别为i和j。翻转字符串t中该子串的末尾字符”a”对应的下标是j=2，在翻转前s中对应的下标为m=length-1-j=4-1-2=1。m对应的是公共子串在原字符串s中首位字符的下标，再加上子串的长度，即m+a[i] [j]-1对应的是公共子串在原字符串s中末尾字符的下标，如果它和i相等，则说明该子串是回文子串。下面，我们来看一下代码的实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[[0 for _ in range(n)] for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[i][j]=1
                else:
                    a[i][j]=a[i-1][j-1]+1

            if a[i][j] > maxlen:
                #翻转前对应的下标
                m=n-1-j
                #判断下标是否对应
                if m+a[i][j]-1==i:
                    maxlen=a[i][j]
                    maxend=i

    return s[maxend-maxlen+1:maxend+1]

print(longestPalindrome("abacd"))

我们从代码可以看出，时间复杂度为O(n2)，空间复杂度也是O(n2)。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3225bdf6-6671-449e-a960-a2822ba75376

我们来分析一下循环逻辑，i=0，然后遍历j=0,1,2,3。更新一列，然后i=1，再更新一列，更新的时候，我们只需要上一列的信息。所以，我们可以用一个一维数组来保存就好了。我们看一下代码实现。

def longestPalindrome(s):
    if s=="":
        return ""
    #字符串反转
    t=s[::-1]
    n=len(s)
    a=[0 for _ in range(n)]
    maxlen=0
    maxend=0
    for i in range(n):
        for j in range(n-1,-1,-1):
            if(s[i]==t[j]):
                if i == 0 or j == 0:
                    a[j]=1
                else:
                    a[j]=a[j-1]+1
            else:
                a[j]=0

            if a[j] > maxlen:
                #翻转前对应的下标
                m=n-1-j
                #判断下标是否对应
                if m+a[j]-1==i:
                    maxlen=a[j]
                    maxend=i

    return s[maxend-maxlen+1:maxend+1]

print(longestPalindrome("abacd"))

所以，我们可以把空间复杂度降低为O(n)。

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:b7895544-8d68-453f-9772-c8082bbfc14c

最后

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:e0149ee4-567b-489f-ac4c-4d4f93a2fea9

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:3bd9a37a-2c48-4b55-a7c1-24dbdbe73150

[TencentCloudSDKException] code:FailedOperation.ServiceIsolate message:service is stopped due to arrears, please recharge your account in Tencent Cloud requestId:5b2ff440-b547-496d-805c-c59eeaefb75d

Original: https://www.cnblogs.com/cxyxz/p/15632590.html
Author: 算法推荐管
Title: 20211202完全对称日，我们一起来温习一下