5. 最长回文子串

一、题目描述

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

示例1：

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

示例2：

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

二、思路

1. 双层循环

• 第一层循环控制元素遍历起始位置
• 第二层循环控制遍历后边的元素
• 把内层循环的元素累加到一个变量 cur 上，每累加一个就判断当前子串cur是否为回文串，并且长度是否大于前边保存的回文子串，条件成立，则对结果更新。

2. 动态规划

首先上LeetCode官方题解

再来一个写的比较好的题解liweiwei1419

---

对于一个子串，并且长度大于2，如果它是回文串，那么去掉两头的元素以后，它依然是回文串。

我们设i、j分别为子串的起始位置和结束位置，用P(i,j)来表示这个子串，那么对于子串P(i,j)是否为回文串就有两种可能：
$$
P(i,j)=\left{
\begin{array}{rcl}
true, & & {如果子串S_i……S_j是回文串}\
false,& & {其他情况}\
\end{array} \right.
$$
可以写出动态规划的状态转移方程为：
$$
P(i,j)=P(i+1,j-1) \and (S_i == S_j)
$$
也就是说，只有s[i+1:j-1]是回文串，并且 s 的第 i 个元素与第 j 个元素相同时，P[i:j]是回文串。

以上为子串长度大于2的情况，下边讨论子串长度小于等于2的情况。

子串长度为1时，子串必是回文串；子串长度为2时，只要这两个元素相同，那么就是回文串。因此我们可以得出动态规划的边界条件：
$$
\left{
\begin{array}
P(i,i)=true\
P(i,i+1)=(S_i==S_j)
\end{array} \right.
$$
根据这个思路，我们就可以完成动态规划了。

三、代码实现

1. 双层循环

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)

        # if length == 0 or length == 1:
        #    return s

        ans = ""
        for i in range(length):
            cur = ""
            for j in range(i, length):
                cur += s[j]
                if cur == cur[::-1] and len(cur) > len(ans):
                    ans = cur
        return ans

2. 动态规划

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        dp = [[False] * length for _ in range(length)]

        res = ""

        # 子串长度实际为n+1
        for n in range(length):
            # 子串开始位置
            for i in range(length):
                # 子串结束位置
                j = i + n

                if j >= length:
                    break
                if n == 0:
                    dp[i][j] = True
                elif n == 1:
                    dp[i][j] = (s[i] == s[j])
                else:
                    dp[i][j] = (dp[i+1][j-1] and (s[i] == s[j]))
                if dp[i][j] and n + 1 > len(res):
                    res = s[i:j+1]
        return res

四、表现

1. 双层循环

method	运行时间	表现	内存消耗	表现
1. 双循环	8176ms	5.01%	13.1MB	97.83%
2. 动态规划	9948ms	5.01%	20.9MB	28.50%