会员专享
请先
登录，登录后可使用今日免费解锁；
开通会员后可解锁完整内容。
思路：动态规划优化枚举
一个朴素的算法是：O(n2) 枚举所有子串，然后O(n)的判断这个子串是否是回文串，总复杂度O(n3)
#code-switcher
class Solution:
def longestPalindrome(self, s: str) -> str:
# 判断 s[left:right] 这一段是否是回文串
def is_palindrome(left, right):
题目内容
给定一个字符串 s。若从 s 中取出一个连续子串，且该子串从左向右阅读和从右向左阅读得到的内容完全一致，就称它为一个回文子串。你的任务是在 s 的所有回文子串中，找出长度最大的一个。
约束条件：字符串 s 的长度满足 1≤∣s∣≤1000，并且 s 仅由数字和英文字母组成。
输入描述
输入包含一个参数：一个字符串 s，表示待搜索的原始字符串。
输出描述
返回一个字符串，表示 s 中最长的回文子串；如果存在多个长度相同的最长回文子串，返回其中任意一个即可。
样例1
输入
z
输出
z
说明
长度为 1 的字符串本身就是回文。
从左到右和从右到左读取都是 z，因此最长回文子串为 z。
样例2
输入
aaaaaa
输出
aaaaaa
说明
整个字符串 aaaaaa 从左到右和从右到左读取完全相同，长度为 6。
由于所有字符都相同，任意子串都是回文，但最长的是整个字符串，所以输出 aaaaaa。
样例3
输入
xabcbay
输出
abcba
说明
整体 xabcbay 不是回文。
从第 2 个字符到第 6 个字符组成的子串是 abcba，反转后仍为 abcba，长度为 5。其他更长的子串都不是回文，因此输出 abcba。
样例4
输入
a1b2b1a
输出
a1b2b1a
说明
整个字符串 a1b2b1a 从左到右和从右到左读取完全相同，长度为 7。
因此最长回文子串就是它本身，输出 a1b2b1a。
