给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
示例 2：
输入: "cbbd"
输出: "bb"
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 暴力求解法
这种方法思路是 : 变量i从索引0开始遍历，变量j从索引i开始，i的边界范围为length，j的边界范围为length + 1 (因为slice方法是左开右闭的区间) ，这样就可以拿到字串(a,ab,abc,abcd...)，双重循环中通过isPalindromic方法判断是否为回文字串，最后更新最长字串的值，时间复杂度为，可以通过93个测试用例。
/**
* @param {string} s
* @return {string}
*/
var isPalindromic = (s)=> {
const len = s.length
for(let i=0;i<len/2;i++) {
if(s.substr(i,1) !== s.substr(len-1-i,1)) {
return false
}
}
return true
}
var longestPalindrome = function(s) {
let ans = '', // 记录值
len = s.length, // 字符串长度
max = 0;
for(let i=0;i<len;i++) {
for(let j=i+1;j<=len;j++) {
// 此时的子串可以这样获得
let palinStr = s.slice(i,j)
if(isPalindromic(palinStr) && palinStr.length > max ) {
// 记录回文字串的值 并更新max
ans = palinStr
max = palinStr.length
}
}
}
return ans
};
这是可以通过的方法，采用了动态规划的方法。主要思路是如果s[l,r]是一个回文字串，那么将它左右各减一个字符串s[l+1,r-1]也是一个回文字串。
var longestPalindrome = function(s) {
const length = s.length
if(length<=1) return s ;
const dp = []
// 初始化二维数组
for(let i=0;i<length;i++) {
dp[i] = []
for(let j=0;j<length;j++) {
dp[i][j] = false
}
}
let max = 1,
res = s[0]
for(let r=1;r<length;r++) {
for(let l=0;l<r;l++) {
// 状态转移方程：如果头尾字符相等并且中间也是回文
// 在头尾字符相等的前提下，如果收缩以后不构成区间（最多只有 1 个元素），直接返回 True 即可
// 否则要继续看收缩以后的区间的回文性
// 重点理解 or 的短路性质在这里的作用
if(s[r] === s[l] && (dp[l + 1][r - 1] ||r-l<=2 ) ) {
dp[l][r] = true
let cur_len = r - l + 1
if( cur_len > max ) {
max = cur_len
res = s.slice(l,r+1)
}
}
}
}
return res
};
