一、描述

二、题解：

2.1 暴力法（ O ( N 3 ) O(N^3) O(N3)）

解释：

循环三次。第一次起始点循环；第二次终止点循环（从最右边开始到起始点为止）；第三次起始点开始终止点结束，当两个值不相等时候跳出循环。只有完整进行第三次循环才满足回文串的条件。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_ = 1
        max_str = s[0]
        length = len(s)
        for i in range(length):
            for j in range(length-1,i,-1):
                k_l = i
                k_r = j
                while(s[k_l] == s[k_r]):
                    if (k_l >= k_r):
                        break
                    else:
                        k_l+=1
                        k_r-=1
                if k_l>=k_r and j - i +1 > max_:
                    max_ = j - i +1
                    max_str = s[i:j+1]
                    break
            if max_ == length:
                break
        return max_str

2.2 动态规划（ O ( N 2 ) O(N^2) O(N2)）

解释：

首先初始化一个维度为length的二维单位阵（对角全为1，其余为0）；判断是否有长度为2的回文串，如有则起始和终止索引在矩阵中对应的位置为1。 递归的思路为当起始点i到终止点j为回文串，则起始点i+1到终止点j-1也是回文串。因此从长度为3开始进行判断，当发现回文串时，修改矩阵对应位置值为1，并进行长度和起始位置的记录。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length= len(s)
        max_ = 1
        max_start = 0
        ## initial matrix
        dst = [[0 for i in range(length)] for _ in range(length)]
        for i in reversed(range(length)):
            dst[i][i]=1
            if(i+1<length and s[i]==s[i+1]):
                dst[i][i+1]=1
                max_ = 2
                max_start=i
        for le in range(3,length+1):
            for i in range(0,length-le+1): 
                if(s[i]==s[i+le-1] and dst[i+1][i+le-2]==1):
                    dst[i][i+le-1] = 1
                    if le > max_:
                        max_ = le 
                        max_start = i
        return s[max_start:max_start+max_]

2.3 中心扩展（ O ( N 2 ) O(N^2) O(N2)）

解释：

从中心向外扩展。 分为两种情况：第一种当回文串长度为奇数的情况；第二种当回文串长度为偶数的情况。 左右同时向外扩展，当左右不相同时停止扩展，记录最长回文串长度及起始位置。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        max_ = 1
        max_start = 0
        length = len(s)
        for i in range(length): # odd
            for k in range(2):
                k_l = i-k # 0 代表偶数，1代表奇数 
                k_r = i+1
                while(k_l>=0 and k_r<length and s[k_l]==s[k_r]):
                    k_l -= 1
                    k_r += 1
                if max_ < k_r - k_l-1:
                    max_ = k_r - k_l-1
                    max_start = k_l+1
        return s[max_start:max_start+max_]

2.4 Manacher（马拉车）算法（ O ( N ) O(N) O(N)）

解释：

利用历史记录及回文串的对称性，来达到跳着位移的目的。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        s = list(s)
        new_s = # + #.join(s) + #
        length = len(new_s)
        P = [0]*length
        c = 0
        r = 0
        maxlen = 0
        max_start = 0
        for i in range(length):
            i_mirror = 2*c-i
            if (i<r):
                P[i] = min(r - i,P[i_mirror])
            k_l = i-(1+P[i])
            k_r = i+(1+P[i])
            while(k_l>=0 and k_r <length and new_s[k_l] == new_s[k_r]):
                P[i] += 1
                k_l -= 1
                k_r += 1
            if i+P[i] > r:
                c = i
                r = i+P[i]
                if P[i] > maxlen:
                    maxlen = P[i]
                    max_start = (i-P[i])//2
        return .join(s[max_start:max_start+maxlen])

如有问题或建议欢迎私信。 严禁私自转载，侵权必究 参考： [1]