LeetCode5 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.

Output: “bb”
解析：
最长回文问题，给定字符返回最长的回文字符，如给定字符串”babad”，返回”bab”，以a为中心左右对称。
方案1：
暴力求解，直接挨个遍历处理，时间复杂度为\(O(n^3)\)。没啥可解释的，直接上代码。
[cc lang=”C++”]
bool isValid(string s, int left, int right)
{
while(left < right) { if(s[left] == s[right]) { left ++; right --; }else { return false; } } return true; } string longestPalindrome(string s) { int len = s.length(); if(len == 0) { return ""; } int max_len = 0; int global_left = 0; int global_right = 0; for(int i=0; i < len; i++)//字符结束位置 { for(int j=0; j< i;j++)//字符的起始位置 { int left = j; int right = i; if(isValid(s,j,i) && max_len < i-j+1) { global_left = j; global_right = i; max_len = i-j+1; } } } string result = s.substr(global_left, global_right - global_left+1); return result; } [/cc] 方案2： 中心扩散法，考虑回文的长度，如果回文长度为奇数，则以一个字符为中心，相互对称；如果回文长度为偶数，则最中心的两个元素相等，其余由内到外对称。所以考虑以一个中心元素往左右扩展，如"aaaa"。时间复杂度为[latex]O(n^2)[/latex] [cc lang="C++"] class Solution { public: string longestPalindrome(string s) { int len = s.length(); if(len <= 1) { return s; } int max_len = 0; int start =0; for(int index=1; index < len; index ++)//遍历每一个元素 { //以index为中心元素长度为奇数的回文 int low = index-1; int high = index + 1; while(low >=0 && high max_len)
{
max_len = high-low -1;
start = low + 1;
}
//以index-1,index为中心的长度为偶数的回文
low = index-1;
high = index;
while(low >=0 && high max_len)
{
max_len = high-low -1;
start = low + 1;
}
}
return s.substr(start, max_len);

}
};
[/cc]

方案3：
Manacher算法，时间复杂度O(n), 空间复杂度O(n)。
后续再补充。。。

参考：
http://www.cnblogs.com/TenosDoIt/p/3675788.html