360弹出网站,t型布局网站实例,南京的电商网站设计,wordpress 码查询问题
给你一个字符串 s#xff0c;找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同#xff0c;则该字符串称为回文字符串。
示例 1#xff1a;
输入#xff1a;s babad
输出#xff1a;bab
解释#xff1a;aba 同… 问题
给你一个字符串 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 中心扩展算法
确定中心回文子Pi,j中心子串是指长度大于等于1的相同字符组成的子串例如“bab”的“a”,“baab”的“aa”“baaab”的“aaa”等从每一种边界情况开始「扩展」也可以得出所有的状态对应的答案。 class Solution:def longestPalindrome(self, s: str) - str:max_longest0max_longest_ss_lenlen(s)longest[[0]*s_len for _ in range(s_len)]for i in range(s_len):longest[i][i] 1left_i,right_ii-1,i1while right_is_len and s[i]s[right_i]:longest[i][right_i]1right_i1while left_i0 and right_is_len:if s[left_i]s[right_i]:longest[i][right_i] 1longest[i][left_i] 1left_i-1right_i1else:breakif right_i-1-left_i-11max_longest:max_longest_ss[left_i1:right_i]max_longestright_i-1-left_i-11# print(longest,max_longest_s)return max_longest_s
方法2 Manacher算法
请自学
