日野弥生：勉強しよう
LeetCode 5 - 最长回文子串
发表于2024年12月22日
回文串的定义是正读反读都一样。很容易想到回文串是以某一段数据为中心，他的左边和他的右边的数据必须一致。从而可以考虑到从头到尾进行遍历，假设每一个元素为回文中心，看左右两边是否满足条件，从而找出最长的子串。获取子串的关键在于起始点和长度。
观察两个测试案例发现，有偶数和奇数两种为中心的区别，考虑用左右元素的方式淡化这样的区别。 注意算法的边界在于字符串长度为1，单独处理。
class Solution {
public:
string longestPalindrome(string s) {
if(s.size()==1)
return s;
int start=0,size=s.size(),maxLen=1;
auto fn=[&](int left, int right)
{
while(left>=0&&right<size&&s[left]==s[right])
{
if(right-left+1>maxLen){
start=left;
maxLen=right-left+1;
}
left--;
right++;
}
};
for(int i=0;i<size;i++)
{
fn(i,i);
fn(i,i+1);
}
return s.substr(start, maxLen);
}
};