5. 最长回文子串
题目链接:5. 最长回文子串
代码如下:
//中心扩散法
//参考:https://leetcode.cn/problems/longest-palindromic-substring/solutions/63641/zhong-xin-kuo-san-fa-he-dong-tai-gui-hua-by-reedfa/comments/1465839
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()<2) return s;
int maxLeft=0;//记录最长回文子串的起点
int maxRight=0;//记录最长回文子串的终点
int maxlen=0;//记录最长回文子串的长度
int len=1;
for(int mid=0;mid<s.size();mid++)
{
int left=mid-1;
int right=mid+1;
//向左侧扩展,直到超过边界或遇到与中心字符不等跳出while循环
while(left>=0&&s[left]==s[mid])
{
left--;
len++;
}
//向右侧扩展,直到超过边界或遇到与中心字符不等跳出while循环
while(right<s.size()&&s[right]==s[mid])
{
right++;
len++;
}
//同时向两侧扩展
while(left>=0&&right<s.size()&&s[left]==s[right])
{
right++;
left--;
len+=2;
}
if(len>maxlen)
{
maxLeft=left;
maxRight=right;
maxlen=len;
}
len=1;
}
return s.substr(maxLeft+1,maxlen);
}
};