[动态规划]最长回文子串
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
解析：
什么叫回文串？
如果一个字符串正着读和反着读是一样的，那它就是回文串。
class Solution {
public:
//动态规划
string longestPalindrome(string s) {
if(s.empty()) return " ";
int length=s.size();
int l=0;
string res=s.substr(0,1);
vector<vector<bool>> dp(length,vector<int>(length,false);
for(int i=0;i<length;++i){
for(int j=i;j>=0;--j{
if(s[i]==s[j]&&(i-j>2||dp[i-1][j+1])){
dp[i][j]==true;
if(i-j>l){
l=i-j;
res=s.substr(j,l+1);
}
}
}
}
return res;
}
//中心扩展法
string longestPalindrome(string s) {
if(s.empty()) return "";
int lmax=0;
string res=s.substr(0,1);
int length=s.size();
int left;
int right;
for(int i=0;i<length;++i){
if(i>=0){
left=i-1;
right=i+1;
while(left>=0&&right<length&&s[left]==s[right]){
if(right-left>lmax){
lmax=right-left;
res=s.substr(left,lmax+1);
}
--left;
++right;
}
}
left=i;
right=i+1;
while(left>=0&&right<length&&s[left]==s[right]){
if(right-left>lmax){
lmax=right-left;
res=s.substr(left,lmax+1);
}
--left;
++right;
}
}
return res;
}
};
还有一个解法，Manacher
这是一个专门用作处理最长回文子串的方法，思想很巧妙，比较难以理解，这里直接借用了别人的讲解方法。其实主要思想是，把给定的字符串的每一个字母当做中心，向两边扩展，这样来找最长的子回文串，这个叫中心扩展法，但是这个方法还要考虑到处理 abba 这种偶数个字符的回文串。Manacher 法将所有的字符串全部变成奇数个字符。