题干
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
Example 1:
Input: “babad”
Output: “bab”
Note: “aba” is also a valid answer.
Example 2:
Input: “cbbd”
Output: “bb”
题解1 73.89%
class Solution {
public:
void isPalindromic(string &s, int left, int right, int &start, int &maxlen)
{
while(left >= 0 && right < s.size() && s[left] == s[right]){
left--; right++;
}
if(right - left - 1 > maxlen){
start = left + 1;
maxlen = right - left - 1;
}
}
string longestPalindrome(string s) {
if(s.size() < 2) return s;
int len = s.size(), maxlen = 0, start = 0;
for(int i=0; i < len; i++)
{
isPalindromic(s, i, i, start, maxlen);
isPalindromic(s, i, i+1, start, maxlen);
}
return s.substr(start, maxlen);
}
};
题解2 99.65% Manacher算法
class Solution {
public:
string longestPalindrome(string s) {
string t = "$#";
for(int i=0; i<s.size(); i++)
{
t += s[i];
t += "#";
}
vector<int> p(t.size(), 0);
int mx = 0, id = 0, resLen = 0, resCenter = 0;
for(int i = 1; i < t.size(); i++)
{
p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
while(t[i + p[i]] == t[i - p[i]]) ++p[i];
if(mx < i + p[i]){
mx = i + p[i];
id = i;
}
if(resLen < p[i]){
resLen = p[i];
resCenter = i;
}
}
return s.substr((resCenter - resLen) / 2 ,resLen - 1);
}
};
