Leetcode(No.5) 最长回文子串

末蓝、 2022-05-17 07:13 218阅读 0赞

# 问题描述： #

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

## **示例：** ##

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

# 思路与分析： #

## 1.动态规划 ##

### 思路： ###

判断一个子串 **S(i, j)** 是否回文：如果 **S\[ i \] = S\[ j \]**，且 **S\[ i+1, j-1 \]**是回文串，则 **S(i, j)** 必定是回文串。

假设矩阵元素 **P(i ,j)** 表示子串 **S(i, j)** 是否回文，由上得出状态转移方程

**P(i, j) = ( P(i+1, j-1) and S\[ i \] == S\[ j \] )**

写出 **Top-down **的递归代码后将其用 **Bottom-up** 的方式改写即可。

### 时间复杂度： ###

填充完矩阵的上三角或者下三角，结果就出来了，显然时间复杂度是**O(n^2)**

## 2.Manacher 's Algorithm ##

大名鼎鼎的马拉车算法，网上介绍很多，这里只讲解下我觉得比较难的地方。

### 思路： ###

遍历字符串的元素，以它为对称中心向两边配对扩展，若扩展长度为L，则以该元素为中心的回文串长度为2L+1，用数组P来记录每个元素的扩展宽度，且在遍历过程中调用这些记录，减少重复的计算，只需扫描一遍即可完成。

先看代码：

### 代码实现（Python）: ###

class Solution(object):  
    def longestPalindrome(self, s):  
        """  
        :type s: str  
        :rtype: str  
        """  
        if s == '':    return ''  
        T = '^'  
        for i in range(len(s)):  
            T += '\#' + s\[i\]  
        T += '\#$'  
        n = len(T)  
        P = \[0 for i in range(n)\]  
        Center, R = 0, 0  
        for i in range(1, n-1):  
            \#求i关于Center的对称点  
            i\_mirror = 2\*Center - i

\#利用对称点求P\[i\]  
            if R > i:  
                \#P\[i'\]超出边界后只能保证P\[i\] >= R-i  
                P\[i\] = min(P\[i\_mirror\], R-i)  
            else:    P\[i\] = 0

\#关于对称点展开  
            while T\[i+1+P\[i\]\] == T\[i-1-P\[i\]\]:  
                P\[i\] += 1  
            print T\[i\],P\[i\]  
            \#及时更新右边界  
            if i + P\[i\] > R:  
                Center = i  
                R = i + P\[i\]  
        max\_p = 0  
        for i in range(n):  
            if P\[i\] > P\[max\_p\]:  
                max\_p = i  
        ans = T\[max\_p-P\[max\_p\] : max\_p+P\[max\_p\]+1\].replace('\#','')  
        print P  
        return ans

### 难点 ###

（1）**P\[i\] = min(P\[i\_mirror\], R-i)**

利用回文串的对称性质，容易得到 **P\[ i \] = P\[ i\_mirror \]**，但这并不总是成立。

假设当前扫描到元素 i ，以它为中心进行扩展，若令 **P\[ i \] = P\[ i\_mirror \]**，可能在配对过程中超出右边界R。

在双侧边界L、R中，我们可以保证匹配，如果超出了边界，

边界外的字符是否也跟它的对称点——边界内的元素匹配呢？————不知道，只能开始新的匹配了。

由于只能保证边界内的对称性，所以P\[ i \]取两者的较小值：到右边界的距离 R-i 以及对称点的 P 值

当R = i时，当前元素 i 与边界重合，对称的元素是自己，考察 **P\[ i\_mirror** \] 是没有意义的，故 **P\[ i \] = 0**

（2）**while T\[i+1+P\[i\]\] == T\[i-1-P\[i\]\]:  
                P\[i\] += 1**

这个while循环用来求当前元素 i 可以向两边扩展多少，为什么访问的元素索引里有P\[ i \]呢？这正是它的另一精妙所在。

**P\[ i \] **表示 i 的扩展宽度，在while循环之前我们已经求了它的初始值，接下来就在它的基础上再进行匹配，相当于复用了之前的计算。这保证了while循环的运行次数是O(1)复杂度的。

粗略地说：

一般的字符串往外扩展几个字符就会失去匹配，while只需执行O(1)次；

如果回文子串特别长，会不会向两边一直遍历完整个子串呢？由于在匹配过程中复用了 **P\[ i \]**，事实上最多只需再匹配大概 i - P\[ i \]次，应该是常数级别的，笔者给不出严格的证明QAQ 但是在纸上手工模拟了一下 **“aaaaaaa”** 的匹配结果，匹配到一半你会发现往后每次只跟开头的两个字符 "\#a" 做匹配，while只执行两次。

### 时间复杂度：**O(n)** ###

一层 for 循环里面套了只执行 O(1) 次的 while 循环，算法整体是 O(n) 复杂度的

# Reference #

[https://leetcode-cn.com/problems/longest-palindromic-substring/solution/][https_leetcode-cn.com_problems_longest-palindromic-substring_solution]

[https_leetcode-cn.com_problems_longest-palindromic-substring_solution]: https://leetcode-cn.com/problems/longest-palindromic-substring/solution/