LeetCode 5 最长回文子串
🟠 中等偏上 https://leetcode.cn/problems/longest-palindromic-substring/description/
思路
枚举中心点，向两边扩展。
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
int start = 0,end = 0;
for(int i = 0;i<n;i++){
int len1 = help(s,i,i);
int len2 = help(s,i,i+1);
int len = max(len1,len2);
if(len>end-start+1){
if(len%2==1){
start = i-1-(len-1)/2+1;
end = i+1+(len-1)/2-1;
}else{
start = i-(len)/2+1;
end = i+1+(len)/2-1;
}
}
}
return s.substr(start,end-start+1);
}
int help(string& s,int left, int right){
while(left>=0&&right<s.size()&&s[left]==s[right]){
left--;
right++;
}
// cout<<right-left+1<<endl;
return right - left-1;
}
};
class Solution {
public:
int get_length(string &s,int left,int right){
int len = 0;
while(left>=0&&right<s.size()){
if(s[left]==s[right]){
left--;
right++;
len++;
}else{
break;
}
}
return len;
}
string longestPalindrome(string s) {
int n = s.size();
if(n==1) return s;
int i = 0;
int res_index = 0,res_length = 0;
while(i<n){
int len1 = 2*get_length(s,i,i+1);//偶
int len2 = 1+2*get_length(s,i,i+2); //奇数
if(len1>len2&&len1>res_length){
res_index = i-len1/2+1;
res_length = len1;
}
if(len2>len1&&len2>res_length){
res_index = i-(len2-1)/2+1;
res_length = len2;
}
i++;
}
// cout<<res_index<<endl;
return s.substr(res_index,res_length);
}
};