最长回文串
大约 1 分钟
Leetcode算法练习第九题：最长回文串
问题描述
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解法一：中心拓展法
每个回文都是中心对称的，这样，对每个可能的对称点(2n-1个)展开，每次记录最大的回文串长度和起始位置即可：
复杂度
首先需要遍历一遍字符串来定位每一个中心点。然后对应每个中心点需要展开最多$$\frac{n}{2}$$的长度，因而时间复杂度为$$O(n^2)$$，空间复杂度O(1)。
Python
class Solution:
def longestPalindrome(self, s: str) -> str:
if s is None:
return
if len(s)<=1:
return s
st,l=0,0
num=len(s)
i,j,k=0,0,1
for i in range(num):
j=0
while i-j>=0 and j+i+1<num and s[i-j]==s[i+j+1]:
j+=1
if l<2*j:
st=i-j+1
l=2*j
k=1
while i-k>=0 and i+k<num and s[i-k]==s[i+k]:
k+=1
if l<2*k-1:
st=i-k+1
l=2*k-1
return s[st:st+l]
C++
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<=1)return s;
int st=0,len=0,i=0,j=0,sz=s.size();
for(int p=0;p<sz;p++){
i=0;
while(p-i>=0 && p+1+i<sz && s[p-i]==s[p+1+i])
i++;
if(len<2*i){
len=2*i;
st=p-i+1;
}
j=1;
while(p-j>=0 && p+j<sz && s[p-j]==s[p+j])
j++;
if(len<2*j-1){
len=2*j-1;
st=p-j+1;
}
}
return s.substr(st,len);
}
};