leetcode 5. 最长回文子串(python)

港控/mmm° 2022-05-14 04:29 270阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

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

**示例 1：**

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

**示例 2：**

输入: "cbbd"
    输出: "bb"

### 1、解法一**（循环暴力求解）** ###

class Solution(object):
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            List , res_list = [] , []
            for i in range(len(s)):
                for j in range(len(s),i,-1):
                    if s[i:j] == s[i:j][::-1]:
                        List.append(j-i)
                        res_list.append(s[i:j])
            if len(res_list) == 0:
                return ""
            else:
                m = List.index(max(List))
                return res_list[m]

果然超时了！！！

### 2. 中心枚举 ###

通过枚举字符串子串的中心而不是起点，向两边同时扩散，依然是逐一判断子串的回文性。这种优化算法比之前第一种算法在最坏的情况下（即只有一种字符的字符串）效率会有很大程度的上升。

class Solution:
        def longestPalindrome(self, s):
            """
            :type s: str
            :rtype: str
            """
            l = len(s)
            if l == 0:
                return ''
            max_length = 0
            palindromic = ''
            for i in range(l):
                x = 1
                while (i - x) >= 0 and (i + x) < l:
                    if s[i + x] == s[i - x]:
                        x += 1
                    else:
                        break
                x -= 1
                if 2 * x + 1 > max_length:
                    max_length = 2 * x + 1
                    palindromic = s[i - x:i + x + 1]
                x = 0
                if (i + 1) < l:
                    while (i - x) >= 0 and (i + 1 + x) < l:
                        if s[i + 1 + x] == s[i - x]:
                            x += 1
                        else:
                            break
                x -= 1
                if 2 * x + 2 > max_length:
                    max_length = 2 * x + 2
                    palindromic = s[i - x:i + x + 2]
            if palindromic == '':
                palindromic = s[0]
            return palindromic

### 3. Manacher’s Algorithm ###

复杂度o(n)o(n)   
有两个主要的步骤:

1.  将所有可能的奇数/偶数长度的回文子串都转换成了奇数长度：在每个字符的两边都插入一个特殊的符号。abba => \#a\#b\#b\#a\#， aba => \#a\#b\#a\#
2.  用数组 P\[i\] 来记录以字符S\[i\]为中心的最长回文子串向左/右扩张的长度，并增加两个辅助变量id和mx，其中 id 为已知的 \{右边界最大\} 的回文子串的中心，mx则为id+P\[id\]，也就是这个子串的右边界。   
    mx−i>p\[j\]:p\[i\]=p\[j\]mx−i>p\[j\]:p\[i\]=p\[j\]   
    mx−i<=p\[j\]:p\[i\]=mx−imx−i<=p\[j\]:p\[i\]=mx−i

![SouthEast][]

# manacher算法
    def manacher(self):
            s = '#' + '#'.join(self.string) + '#'               # 字符串处理，用特殊字符隔离字符串，方便处理偶数子串
            lens = len(s)
            f = []                                          # 辅助列表：f[i]表示i作中心的最长回文子串的长度
            maxj = 0                                        # 记录对i右边影响最大的字符位置j
            maxl = 0                                        # 记录j影响范围的右边界
            maxd = 0                                        # 记录最长的回文子串长度
            for i in range(lens):                           # 遍历字符串
                if maxl > i:
                    count = min(maxl-i, int(f[2*maxj-i]/2)+1)  # 这里为了方便后续计算使用count，其表示当前字符到其影响范围的右边界的距离
                else :
                    count = 1
                while i-count >= 0 and i+count < lens and s[i-count] == s[i+count]:  # 两边扩展
                    count += 1
                if(i-1+count) > maxl:                         # 更新影响范围最大的字符j及其右边界
                    maxl, maxj = i-1+count, i
                f.append(count*2-1)
                maxd = max(maxd, f[i])                       # 更新回文子串最长长度
            return int((maxd+1)/2)-1                        # 去除特殊字符

### 4. 动态规划 ###

基本思路是对任意字符串，如果头和尾相同，那么它的最长回文子串一定是去头去尾之后的部分的最长回文子串加上头和尾。如果头和尾不同，那么它的最长回文子串是去头的部分的最长回文子串和去尾的部分的最长回文子串的较长的那一个。   
P\[i,j\]P\[i,j\]表示第i到第j个字符的回文子串数   
dp\[i,i\]=1dp\[i,i\]=1   
dp\[i,j\]=dp\[i+1,j−1\]+2|s\[i\]=s\[j\]dp\[i,j\]=dp\[i+1,j−1\]+2|s\[i\]=s\[j\]   
dp\[i,j\]=max(dp\[i+1,j\],dp\[i,j−1\])|s\[i\]!=s\[j\]

def longestPalindrome(s):
            n = len(s)
            maxl = 0
            start = 0
            for i in xrange(n):
                if i - maxl >= 1 and s[i-maxl-1: i+1] == s[i-maxl-1: i+1][::-1]:
                    start = i - maxl - 1
                    maxl += 2
                    continue
                if i - maxl >= 0 and s[i-maxl: i+1] == s[i-maxl: i+1][::-1]:
                    start = i - maxl
                    maxl += 1
            return s[start: start + maxl]

本文仅作学习用途，原文链接：[https://blog.csdn.net/asd136912/article/details/78987624][https_blog.csdn.net_asd136912_article_details_78987624]

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test
[SouthEast]: /images/20220514/9516a9483cce4c548c65daf52a62fe25.png
[https_blog.csdn.net_asd136912_article_details_78987624]: https://blog.csdn.net/asd136912/article/details/78987624