【LeetCode】5、最长回文子串

5、Longest Palindromic Substring最长回文子串

难度：中等

题目描述

英文：

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
中文：

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

示例

Example 1:

1
2
3

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

1 2	Input: "cbbd" Output: "bb"

解题思路

思路一

动态规划方法，维护一个二维数组$tags$，其中$tags[i][j]$表示字符串区间$[i,j]$是否为回文串，当$i=j$时，字符串只有一个字符，肯定是回文串，当$j=i+1$时，字符串为相邻的两个字符，需要判断$s[i]$是否等于$s[j]$，如果$i$和$j$不相邻，即$j-i\ge2$时，除了判断$s[i]$和$s[j]$是否相等，还要判断$tags[i+1][j-1]$是否为真，则有如下递推式：

$tags[i][j]= \begin{cases} 1, & \text{if $i==j$}\\ s[i]==s[j],&\text{if $j=i+1$}\\ s[i]==s[j]\ \&\&\ tags[i+1][j-1],& \text{if $j>i+1$} \end{cases}$

代码提交

Python3，用时6708ms，内存21.9M

时间复杂度：$O(n^2)$

class Solution:
    def longestPalindrome(self, s):
        length = len(s)
        if length <= 1:
            return s

        # 初始化二维数组 tags
        # 不可以用 tags = [[False]*length]*length 的方式，深浅拷贝
        tags = [[False for col in range(length)] for row in range(length)]
        left = 0
        right = 0
        templen = 0
        for j in range(length):
            # if i==j
            tags[j][j] = True
            # j > i
            for i in range(j):
                tags[i][j] = (s[i] == s[j] and (j-i < 2 or tags[i+1][j-1]))
                # 更新当前记录的最长回文子串信息
                if tags[i][j] and templen < j-i+1:
                    left = i
                    right = j
                    templen = j-i+1
        return s[left:right+1]

思路二

参考链接

弱鸡的讲说，这个思路是一致的，但是代码没太看明白。。。

根据回文的特性，一个大回文按比例缩小后的字符串也必定是回文，比如ABCCBA，那BCCB肯定也是回文。所以我们可以根据动态规划的两个特点：
（1）把大问题拆解为小问题
（2）重复利用之前的计算结果
这道题。如何划分小问题，我们可以先把所有长度最短为1的子字符串计算出来，根据起始位置从左向右，这些必定是回文。然后计算所有长度为2的子字符串，再根据起始位置从左向右。到长度为3的时候，我们就可以利用上次的计算结果：如果中心对称的短字符串不是回文，那长字符串也不是，如果短字符串是回文，那就要看长字符串两头是否一样。这样，一直到长度最大的子字符串，我们就把整个字符串集穷举完了。

代码提交

Python3，用时160ms，内存13M

class Solution:
    def longestPalindrome(self, s):
        # 使用动态规划，用空间换时间，把问题拆分
        # 获取字符串s的长度
        str_length = len(s)
        # 记录最大字符串长度
        max_length = 0
        # 记录位置
        start = 0
        # 循环遍历字符串的每一个字符
        for i in range(str_length):
            # 如果当前循环次数-当前最大长度大于等于1  并  字符串[当前循环次数-当前最大长度-1:当前循环次数+1]  == 取反后字符串
            if i - max_length >= 1 and s[i-max_length-1: i+1] == s[i-max_length-1: i+1][::-1]:
                # 记录当前开始位置
                start = i - max_length - 1
                # 取字符串最小长度为2，所以+=2，s[i-max_length-1: i+1]
                max_length += 2
                continue
            # 如果当前循环次数-当前最大长度大于等于0  并  字符串[当前循环次数-当前最大长度:当前循环次数+1]  == 取反后字符串
            if i - max_length >= 0 and s[i-max_length: i+1] == s[i-max_length: i+1][::-1]:
                start = i - max_length
                # 取字符串最小长度为1，所以+=1，s[i-max_length: i+1]
                max_length += 1
        # 返回最长回文子串
        return s[start: start + max_length]

思路三

解决最长回文子串的一个时间复杂度为$O (n)$的算法——Manacher算法。

还没有仔细看，应该是针对该问题的一个比较巧妙的算法。

可参考：最长回文子串——Manacher 算法，LeetCode]最长回文子串（Longest Palindromic Substring）。