题目：
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
方法一：动态规划
var longestPalindrome = function(s) {
let res = '';
let n = s.length;
let dp = Array.from(new Array(n),() => new Array(n).fill(0));
for(let i = n - 1;i >= 0; i--){
for(let j = i;j < n; j++){
dp[i][j] = s[i] === s[j] && (j - i < 2 || dp[i + 1][j - 1]);
if(dp[i][j] && j - i + 1 > res.length){
res = s.substring(i, j + 1)
}
}
}
return res;
};
方法二：中心扩展算法
var longestPalindrome = function(s) {
let res = '', start = 0, end = 0;
let len = s.length;
var getMax = function(i, j) {
while(i >= 0 && j < len && s[i] === s[j]){
i --;
j ++;
}
return j - i - 1;
}
for(let i = 0;i < len; i++){
let a = getMax(i, i);
let b = getMax(i, i + 1);
let max = Math.max(a, b);
if(max > end - start){
start = i - ((max - 1) >> 1);
end = i + ((max) >> 1);
}
}
return s.substring(start,end+1);
};
