5. 最长回文子串

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

示例 1：

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

示例 2：

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/longest-palindromic-substring

1. 暴力法

最先想到的应该是暴力法。

这中间是有很多优化的想法的。

从头开始两层 for 循环截取字符串，然后判断字符串是否回文是最基本的想法。

但是这样的循环会出现很多重复的操作。

但是可以换一种思路。取头index1，尾index2。

循环头index1，循环尾index2，判断截取出来的字符串是否是回文串，如果不是，index2自减。

​ 循环尾 index2：

​ 判断截取出来的字符串是否是回文串，如果不是，index2 自减。

如果是，那么要和之前保存的最长的回文串ret进行长度比较。如果比ret长，则替换。

==直接跳出第二层循环==，因为本次外循环中，就算有index2还满足条件，那也比ret短了。

这是一个剪枝操作。leetcode上的时间大概是1600ms，虽然通过了，但是不太满意。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        length = len(s)
        ret = ""
        # 从头index1开始
        for index1 in range(length):
            # 从尾index2开始
            for index2 in range(-1, -(length + 1), -1):
                # 如果两者相同，那么才判断是否相同。不同肯定不是回文串。
                if s[index1] == s[index2]:
                    # 截取字符串并反转判断是否是回文串
                    str1 = s[index1:index2 + length + 1]
                    str2 = str1[::-1]
                    if str1 == str2:
                        if len(str1) > len(ret):
                            ret = str1
                        # 如果是，那么不管怎么样都退出内循环。
                        break
        return ret

2. 中心拓展法

我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有2n - 1个这样的中心。

你可能会问，为什么会是 2n−1 个，而不是 n 个中心？

原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如 “abba” 的中心在两个‘b’ 之间）。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s is None or len(s) < 1:
            return ""
        start = 0
        end = 0
        for i in range(len(s)):
            # 从i的位置开始向两侧检索，分界线在i。长度一定是奇数。
            len1 = self.expandAroundCenter(s, i, i)
            # 从i和i+1的位置向两侧检索，分界线在中间。长度一定是偶数。
            len2 = self.expandAroundCenter(s, i, i+1)
            length = max(len1, len2)
            if length > end - start + 1:
                # 如果长度是偶数，则左边界向右挪1，
                # 如果是奇数，这样操作的数值是不会变的。
                start = i - (length - 1) // 2
                # 向后的正常取值就可以了，本身就是向后扩展的。
                end = i + length // 2
        return s[start:end + 1]

    def expandAroundCenter(self, s: str, left: int, right: int):
        L, R = left, right
        while L >= 0 and R < len(s) and s[L] == s[R]:
            L -= 1
            R += 1
        return R - L - 1

5. 动态规划

解决这类 “最优子结构” 问题，可以考虑使用 “动态规划”：

1、定义 “状态”； 2、找到 “状态转移方程”。

记号说明： 下文中，使用记号 s[l, r] 表示原始字符串的一个子串，l、r 分别是区间的左右边界的索引值，使用左闭、右闭区间表示左右边界可以取到。举个例子，当 s = 'babad' 时，s[0, 1] = 'ba' ，s[2, 4] = 'bad'。

1、定义 “状态”，这里 “状态”数组是二维数组。

dp[l][r] 表示子串 s[l, r]（包括区间左右端点）是否构成回文串，是一个二维布尔型数组。即如果子串 s[l, r] 是回文串，那么 dp[l][r] = true。

2、找到 “状态转移方程”。

首先，我们很清楚一个事实：

1、当子串只包含 1 个字符，它一定是回文子串；

2、当子串包含 2 个以上字符的时候：如果 s[l, r] 是一个回文串，例如 “abccba”，那么这个回文串两边各往里面收缩一个字符（如果可以的话）的子串 s[l + 1, r - 1] 也一定是回文串，即：如果 dp[l][r] == true 成立，一定有 dp[l + 1][r - 1] = true 成立。

根据这一点，我们可以知道，给出一个子串 s[l, r] ，如果 s[l] != s[r]，那么这个子串就一定不是回文串。如果 s[l] == s[r] 成立，就接着判断 s[l + 1] 与 s[r - 1]，这很像中心扩散法的逆方法。

事实上，当 s[l] == s[r] 成立的时候，dp[l][r] 的值由 dp[l + 1][r - l] 决定，这一点也不难思考：当左右边界字符串相等的时候，整个字符串是否是回文就完全由“原字符串去掉左右边界”的子串是否回文决定。但是这里还需要再多考虑一点点：“原字符串去掉左右边界”的子串的边界情况。

1、当原字符串的元素个数为 3 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 1 个字符，它一定是回文串，故原字符串也一定是回文串；

2、当原字符串的元素个数为 2 个的时候，如果左右边界相等，那么去掉它们以后，只剩下 0 个字符，显然原字符串也一定是回文串。

把上面两点归纳一下，只要 s[l + 1, r - 1] 至少包含两个元素，就有必要继续做判断，否则直接根据左右边界是否相等就能得到原字符串的回文性。而“s[l + 1, r - 1] 至少包含两个元素”等价于 l + 1 < r - 1，整理得 l - r < -2，或者 r - l > 2。

综上，如果一个字符串的左右边界相等，以下二者之一成立即可： 1、去掉左右边界以后的字符串不构成区间，即“ s[l + 1, r - 1] 至少包含两个元素”的反面，即 l - r >= -2，或者 r - l <= 2； 2、去掉左右边界以后的字符串是回文串，具体说，它的回文性决定了原字符串的回文性。

于是整理成“状态转移方程”：

dp[l, r] = (s[l] == s[r] and (l - r >= -2 or dp[l + 1, r - 1]))

或者

dp[l, r] = (s[l] == s[r] and (r - l <= 2 or dp[l + 1, r - 1]))

编码实现细节：因为要构成子串 l 一定小于等于 r ，我们只关心 “状态”数组“上三角”的那部分取值。理解上面的“状态转移方程”中的 (r - l <= 2 or dp[l + 1, r - 1]) 这部分是关键，因为 or 是短路运算，因此，如果收缩以后不构成区间，那么就没有必要看继续 dp[l + 1, r - 1] 的取值。

读者可以思考一下：为什么在动态规划的算法中，不用考虑回文串长度的奇偶性呢。想一想，答案就在状态转移方程里面。

具体编码细节在代码的注释中已经体现。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        size = len(s)
        if size <= 1:
            return s
        # 二维 dp 问题
        # 状态：dp[l,r]: s[l:r] 包括 l，r ，表示的字符串是不是回文串
        # 设置为 None 是为了方便调试，看清楚代码执行流程
        dp = [[False for _ in range(size)] for _ in range(size)]

        longest_l = 1
        res = s[0]

        # 因为只有 1 个字符的情况在最开始做了判断
        # 左边界一定要比右边界小，因此右边界从 1 开始
        for r in range(1, size):
            for l in range(r):
                # 状态转移方程：如果头尾字符相等并且中间也是回文
                # 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
                # 否则要继续看收缩以后的区间的回文性
                # 重点理解 or 的短路性质在这里的作用
                if s[l] == s[r] and (r - l <= 2 or dp[l + 1][r - 1]):
                    dp[l][r] = True
                    cur_len = r - l + 1
                    if cur_len > longest_l:
                        longest_l = cur_len
                        res = s[l:r + 1]
            # 调试语句
            # for item in dp:
            #     print(item)
            # print('---')
        return res

以上需要相当长时间的理解和阅读。

4. 膜拜大佬

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if (len(s) <= 1) or s == s[::-1]:
            return s
        start = 0
        maxlen = 0
        for i in range(len(s)):
            str1 = s[i - maxlen: i + 1]
            str2 = s[i - maxlen - 1: i + 1]

            if (i - maxlen) >= 0 and (str1 == str1[::-1]):
                start, maxlen = i - maxlen, len(str1)
            if (i - maxlen - 1) >= 0 and (str2 == str2[::-1]):
                start, maxlen = i - maxlen - 1, len(str2)
        return s[start: start + maxlen]

贴上大佬代码贡阅读。

不太理解。。。。