最长回文子串
题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解题思路
- 中心扩散的方法
- 按照回文的理解，回文中心两侧其实是互为镜像的。那么回文就可以从它的中心展开。
- 回文子串长度可能为奇数，也可能为偶数。奇数的情况下，回文中心就是中间的字符，偶数的情况下，回文中心就是中间两个字符之间的空隙。
- 这里借助一个扩散的函数，传入的值是字符的索引值。如果传入的索引值是重合的，那么扩散所得的回文子串长度是奇数；若是传入的索引值是相邻的，那么得到的回文子串则是偶数的。
代码实现
class Solution:
def longestPalindrome(self, s: str) -> str:
length = len(s)
if length < 2:
return s
max_sub_len = 1
start = 0
for i in range(length):
# 同时对两种情况进行扩散
# 单字符的情况，或者两字符之间空隙为中心的情况
odd_sub_len = self.__expand_around_center(s, length, i, i)
even_sub_len = self.__expand_around_center(s, length, i, i + 1)
# 比较两种情况返回的子串长度，取大值
sub_len = max(odd_sub_len, even_sub_len)
if sub_len > max_sub_len:
max_sub_len = sub_len
# 调整子串的起始位置，
# 若是传入相邻的值，是以左边值的索引为基准的
# 这时中心在两值之间的空隙，调整起始位置注意 -1
# 若是传入的值是重合的，也就是字符为中心，这种方法同样适用，等同手动向下取整
start = i - (sub_len - 1) // 2
return s[start:start + max_sub_len]
def __expand_around_center(self, s, length, left, right):
# 如果传入的值 left = right，是奇数回文子串
# 如果传入的值 left + 1 = right，也就是相邻的值，则是偶数回文子串
i = left
j = right
# 符合条件，向左右两边扩散
while i >= 0 and j < length and s[i] == s[j]:
i -= 1
j += 1
# 返回子串的长度
return j - i -1
实现效果
本次使用的方法是中心扩散的方法，解决最长回文子串的问题。运用的思想就是回文中心左右两侧互为镜像的原理。
还有一种方法叫 “Manacher 算法”，用以专门解决“最长回文子串”的方法，这里不展开说明。但是有兴趣了解的话，推荐大家可以看看下面这位作者在题解中关于这个算法的描述，看下来觉得非常详细，非常 6。
以上就是本篇的主要内容