最长回文子串leetcode-5

题目：给定一个字符串 s，找到 s 中最长的回文子串（关于中心对称）。你可以假设 s 的最大长度为 1000。

示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

1.中心扩散法

分析

子串的字符长度数可能是奇数或者偶数，所以可以是相邻的字符相等（偶数个），或者中间隔一个相等（奇数个），因此如果遇到这样的情况，就回头看是否能够对长度扩大。（注意边界条件即可）时间复杂度为 $O(n^2)$ 因为内部最多可以回溯到整个待搜索字符的长度。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        if len(s)<=1:
            return s
        i = 0
        res = s[0]
        while i <len(s)-1:
            if s[i] == s[i+1]:
                res1= self.backandforw(s,i,i+1)
                if len(res1)>len(res):
                    res = res1
            if i+2<len(s) and s[i] ==s[i+2]:
                res1= self.backandforw(s,i,i+2)
                if len(res1)>len(res):
                    res = res1
            i+=1
        return res
    def backandforw(self,s,back,forw):
        while back>0 and forw<len(s)-1 and s[back-1]==s[forw+1]:
                    back-=1
                    forw+=1
        return s[back:forw+1]

2.动态规划法

动态和规划和递归类似都要构造可反复利用的结构
这里就要找出前一步和后一步的关系
如果我们用二维数组来存储结果，其中sign[i][j]表示从s[i]到s[j]是否是回文子串，那么sign[i-1][j+1]就可以用上一步的结果直接进行判断，而不用再去回溯了。边界情况就是i=j，肯定是1的，以及i+1=j的时候，只需要判断这一个字符相等即可赋值为1。但是这里要注意顺序，从后往前是更好的思路。
动态规划的好处是可以存储全部的回文子串。

class Solution:
    def longestPalindrome(self, s):
        sign = [[0 if i!=j else 1for i in range(len(s))] for j in range(len(s))]
        longest = s[0]
        for i in range(len(s)-1,-1,-1):
            for j in range(len(s)-1,i,-1):
                if s[i] == s[j]:
                    if i+1<=j-1 and sign[i+1][j-1]==1:
                        sign[i][j]=1
                        if 1+j-i>len(longest):
                            longest=s[i:j+1]
                    elif i+1==j:
                        sign[i][j]=1
                        if 1+j-i>len(longest):
                            longest=s[i:j+1]
        return longest

动态规划要谨记的一点，有时候并不需要一定要在最后一步得到结果，可以得到局部结果后，再去遍历回顾。否则会在思维上造成构造困难的局面，掉进思维陷阱。