LeetCode 5
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 输入: “babad” 输出: “bab” 注意: “aba” 也是一个有效答案。
示例 2： 输入: “cbbd” 输出: “bb”
分析：
最长回文子串去头去尾一定也是回文子串，所以使用动态规划，用一个二维数组将之前遍历结果保存下来。用两个变量一头一尾去遍历输入字符串，如果相等就判断他们中间是否是回文子串，如果是，就更新最长子串。 注意left要从最右开始递减，right从left的位置开始递增。
C++代码
class Solution {
public:
string longestPalindrome(string s) {
if(s.length() == 0)
return "";
string res;
bool flag[1000][1000] ={false};
int max = 0;
int left, right;
for(int i = s.length() - 1; i >= 0; i--){
for(int j = i; j <= s.length(); j++){
if(s[i] == s[j] && (j - i <= 2 || flag[i+1][j-1] == true)){
flag[i][j] = true;
if(max < j - i + 1){
max = j - i + 1;
left = i;
right = j;
//if(i>0 && j < s.length())
// printf("%d, %d, %d\n", i, j, flag[i+1][j-1]);
}
}
}
}
res = s.substr(left,max);
return res;
}
};
