网站建设费用5万入账免费seo网站自动推广
问题
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd" 输出："bb"
提示：
1 <= s.length <= 1000s仅由数字和英文字母组成
题解
方法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算法
请自学