Leetcode 5. 最长回文子串

题目描述

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"

输出: "bab"

注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"

输出: "bb"

解法1

动态规划，以 表示字符串中下标 到 的字符串是否为回文串，包括首尾下标字符，若 。则有：

借助二维数组记录 记录 状态。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret,flag='',[[False]*len(s) for i in range(len(s))]
        for j in range(len(s)):
            for i in range(j,-1,-1):
                if s[i]==s[j]:
                    if j-i<3 or flag[i+1][j-1]:
                        flag[i][j]=True
                        ret=s[i:j+1] if j-i+1>len(ret) else ret
        return ret

解法2

解法1借助了二维数组空间来完成计算，这里优化数组空间为一维数组。

由解法1可知，对于下标 的一维数组空间 :

表示 是否为回文串。

对于下标 的一维数组空间 ，如果 ，则 取决于 。这里可以使用一维数组 记录状态，则 取决于 。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        ret,flag='',[False]*len(s)
        for j in range(len(s)):
            for i in range(j+1):
                if s[i]==s[j] and (j-i<3 or flag[i+1]):
                    flag[i]=True
                    ret=s[i:j+1] if j-i+1>len(ret) else ret
                else:
                    flag[i]=False
        return ret

解法3

前面两种解法都需要 的计算复杂度，解法3采用 manacher 算法，首先使用字符串中不存在的字符，扩充原始字符串，以此忽略奇数和偶数长度的影响。然后由左向右遍历字符串中元素，以每个元素为对称轴，扩散求回文串长度。

若是填充后进行常规的扩散求回文串，则复杂度依然是 ，manacher 算法中记录已访问回文串最右元素下标 maxrt，及当前的对称轴下标 cen。则继续访问时，若元素下标 i 在 maxrt 之前，根据对称性，以 i 位置为对称轴的回文串已全部访问，或已访问 s[i:maxrt+1] 部分，剩下的部分可继续访问。通过该方式避免了对每个下标位置的重复扩散访问，满足 的计算复杂度。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s='#'+'#'.join(list(s))+'#'
        ret,m,cen,maxrt='',[0]*len(s),0,0
        for i in range(len(s)):
            if i<maxrt:
                m[i]=min(m[2*cen-i],maxrt-i)
            while i-m[i]-1>=0 and i+m[i]+1<len(s) and s[i-m[i]-1]==s[i+m[i]+1]:
                m[i]+=1
            if i+m[i]>maxrt:
                cen,maxrt=i,i+m[i]
            if m[i]>len(ret):
                ret=s[i-m[i]:i+m[i]+1].replace('#','')
        return ret