网站 不稳定长春做网站好的公司

问题

给你一个字符串 s，找到 s 中最长的回文子串。

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。

示例 2：

输入：s = "cbbd"
输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

题解

方法1：动态规划

对于一个子串而言，如果它是回文串，并且长度大于 222，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是“a”。

那么我们就可以写出动态规划的状态转移方程：

	if len(s)<=2
	else

中心扩展算法

• 确定中心回文子：P（i,j）中心子串是指长度大于等于1的相同字符组成的子串，例如“bab”的“a”,“baab”的“aa”，“baaab”的“aaa”等
• 从每一种边界情况开始「扩展」，也可以得出所有的状态对应的答案。

class Solution:def longestPalindrome(self, s: str) -> str:max_longest=0max_longest_s=""s_len=len(s)longest=[[0]*s_len for _ in range(s_len)]for i in range(s_len):longest[i][i] = 1left_i,right_i=i-1,i+1while right_i<s_len and s[i]==s[right_i]:longest[i][right_i]=1right_i+=1while left_i>=0 and right_i<s_len:if s[left_i]==s[right_i]:longest[i][right_i] = 1longest[i][left_i] = 1left_i-=1right_i+=1else:breakif right_i-1-left_i-1+1>max_longest:max_longest_s=s[left_i+1:right_i]max_longest=right_i-1-left_i-1+1# print(longest,max_longest_s)return max_longest_s

方法2 Manacher算法

请自学