题目介绍
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
示例 2：
输入：s = "cbbd"
输出："bb"
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成
Tags
string | dynamic-programming
Companies
amazon | bloomberg | microsoft
题解
这道题是一道经典的动态规划题，需要用到动态规划的思想。
首先是判断回文串，通过比较中心的两个字符是否相等来判断。可以在利用双指针来实现，先从两端开始遍历，如果两个字符相等，则继续向中心移动，不相等则返回false，遍历结束返回true。因为第二个指针相对于第一个指针是镜像的，所以第二个指针可以可以直接用字符串长度 - 第一个指针位置 - 1实现。
其次是对整体的字符串进行遍历，找出最长的字符串。从第二个开始遍历，当然要进行一个边界条件判断，只有一个字符的时候，直接返回即可。这里也是利用双指针进行遍历，第一个指针位置从头遍历到尾，下一个指针从头遍历到第一个指针的位置之前的一位，获取一个临时字符串进行判断，如果临时字符串是回文串，则更新最长回文串。这里可以这样优化，将第二个指针放在最大最大回文串长度之前，这样可以减少遍历的次数。
/*
* @lc app=leetcode.cn id=5 lang=javascript
*
* [5] 最长回文子串
*/
// @lc code=start
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
// 回文串判断
function judge(tmp) {
const len = tmp.length;
const mid = Math.floor(len / 2);
// 奇偶字符串都遍历一半就好了，中间的字符可以无视
for (let i = 0; i < mid; i++) {
if (tmp[i] != tmp[len - 1 - i]) return false;
}
return true;
}
let len = s.length;
// 边界条件，只有一个字符的时候，直接返回即可
if (len <= 1) return s;
// 存储最长回文串，第一项为长度第二项为字符串
let maxRes = [1, s[0]];
// 从第二个开始遍历
for (let i = 1; i < len;i++) {
for (let j = 0; j < i; j++) {
let dif = i - j + 1;
// 如果截取的字符串长度小于最大长度，则跳过
if (dif <= maxRes[0]) break;
let tmpArray = s.slice(j, i + 1);
// 判断回文串，如果是回文串，则更新最长回文串
if(judge(tmpArray) && dif > maxRes[0]) {
maxRes[0] = dif;
maxRes[1] = tmpArray;
}
}
}
return maxRes[1];
};