Longest Palindromic Substring 题解
题目来源：Longest Palindromic Substring
> Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.
解题思路：
暴力搜索, \(O(N^2) \)
最简单的方法就是选中i(0~n-1)，然后向两边扩展，复杂度为\(O(N^2) \) . 注意回文长度可能是奇数或者偶数， 即 aba or abba
string longestPalindrome(string s)
{
int n = s.length();
if (n <= 1) return s;
int start = 0; int maxLen = 1;
for(int i = 0; i < n; i++)
{
//center: i
int left = i - 1;
int right = i + 1;
while(left >= 0 && right < n
&& s[left] == s[right])
--left, ++right;
//s[left] != s[right] , s[left+1 : right-1] is palindrome
int len = (right-1) - (left+1) + 1;
if(len > maxLen)
start = left+1, maxLen = len;
//center: between s[i] and s[i+1]
if(i+1 < n && s[i] == s[i+1])
{
left = i;
right = i+1;
while(left >= 0 && right < n
&& s[left] == s[right])
--left, ++right;
len = (right-1) - (left+1) + 1;
if(len > maxLen)
start = left+1, maxLen = len;
}
}
return s.substr(start, maxLen);
}或者可以这样，将中间相同的字符跳过，不考虑奇数还是偶数的串(其实还是考虑了，也包括在内了)。
DP, \(O(N^2) \)
dp[i][j] 表示 s[i:j] 是回文, 当且尽当s[i] == [j] && dp[i+1][j-1], 即计算dp[i][j]时, dp[i+1][j-1]得先计算出来，算dp[x][i]，必须先把dp[x][i-1]先计算出来了来。
计算s[:5]的结果，先得把所有s[:4]结尾的回文算出来了来。 上面比如在算dp[i][5]时，用到了dp[x][4]，在上面的循环中,dp[x][4]已经算出来了的。 另外，虽然都是平方的算法，上面用vector还过不了，用数组才能过。
\( O(n) \) 算法, Manacher 算法
felix021的文章讲得很清楚，这里“偷”过来。
>
代码如下：
Last updated
Was this helpful?