5. 最长回文子串

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

示例 1：

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

示例 2：

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

思路--中心扩散法

枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
注意：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的：
1、奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "b"；
2、偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。
可以设计一个方法，兼容以上两种情况：
1、如果传入重合的索引编码，进行中心扩散，此时得到的回文子串的长度是奇数；
2、如果传入相邻的索引编码，进行中心扩散，此时得到的回文子串的长度是偶数。

python3解法

class Solution:
    def longestPalindrome(self, s: str) -> str:
        start, end = 0, 0
        # 枚举所有可能作为回文子串的中心位置：遍历字符串中的每一个字符，依次作为扩散中心
        for i in range(len(s)):
            # 枚举的时候需要考虑回文子串长度的奇偶性
            # 也就是说回文中心可能是一个字符，也有可能是两个相邻的字符字符：奇数回文子串的中心是一个字符，偶数回文子串的中心是两个字符
            # 对于每一个扩散中心，分别计算奇偶两种情况，并得到回文子串的开始和其实索引的位置left, right
            # odd
            left1, right1 = self.centerexpand(s, i, i)
            if right1 - left1 > end - start:
                start, end = left1, right1
            # even
            left2, right2 = self.centerexpand(s, i, i + 1)
            if right2 - left2 > end - start:
                start, end = left2, right2
        # 最后根据得到的回文子串的开始和结束索引值截取字符串
        return s[start: end + 1]
    # 根据回文中心，得到回文字符串的开始和结束索引值
    def centerexpand(self, s, left, right):
        # 判断方法为：如果两边的字符都相同s[left] == s[right] 就一直向两边扩散，直到两边的字符不相同s[left] ！= s[right]，就停止扩散
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return left + 1, right - 1

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。