> 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);
}
或者可以这样，将中间相同的字符跳过，不考虑奇数还是偶数的串(其实还是考虑了，也包括在内了)。
abbbbbbbbba, left=1时,right一直走到最后一个b, 然后往两边判断是否相等.
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++)
{
int left = i;
int right = i;
while(right+1 < n && s[right+1] == s[left])
++right;
//s[right+1] != s[left], s[right]=s[left]
i = right; //skip the same char
//a[bbbbbbbb]a
while(left-1 >= 0 && right+1 < n
&& s[left-1] == s[right+1])
--left, ++right;
//s[left : right] is palindrome
int len = right - left + 1;
if(len > maxLen)
start = left, maxLen = len;
}
return s.substr(start, maxLen);
}
