题目
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1：
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例2：
输入: “cbbd”
输出: “bb”
解题
方法1（动态规划）：
这题的动态规划法就一个核心思想，保证s[i]===s[j]的同时，保证s[i+1]=s[j-1]，这种算法时间复杂度是O（n^2）,代码：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
const len = s.length;
if (len <= 1) {
return s;
}
let maxLength = 1;
let maxStr = s.substring(0, 1); // 将最小值设置为1，最小字符串设置为第一个字符
const p = [];
for (let i = 0; i < len; i++) {
p[i] = new Array(len);
}
for (let r = 1; r < len; r++) {
for (let l = 0; l < r; l++) {
if (s[l] === s[r] && (r - l <= 2 || p[l + 1][r - 1])) {
p[l][r] = true;
if (r - l + 1 > maxLength) {
maxLength = r - l + 1;
maxStr = s.substring(l, r + 1);
}
}
}
}
return maxStr;
}
执行结果：
我们可以看到，执行效率和内存占用在所有提交的代码中都不是很靠前。
方法2（中心扩展法）：
中心扩展法，顾名思义，找对称中心，来进行查询该对称中心的回文数有多长，对称中心总共有2n-1个（因为包含奇对称和偶对称的情况），然后保存最长的起止位置，最后返回，这种算法时间复杂度也是O(n^2)，代码如下：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
if (s == null || s.length < 1) return "";
let start = 0, end = 0;
for (let i = 0; i < s.length; i++) {
// 查询以i为中心和以（i+1+1）/2为中心的长度
let len1 = expandAroundCenter(s, i, i);
let len2 = expandAroundCenter(s, i, i + 1);
let len = Math.max(len1, len2);
// 如果此位置为中心的回文数长度大于之前的长度，则进行处理
if (len > end - start) {
start = i - Math.floor((len - 1) / 2);
end = i + Math.floor(len / 2);
}
}
return s.substring(start, end + 1);
}
// 查询s在left，right位置的对称长度
function expandAroundCenter(s, left, right) {
let L = left, R = right;
while (L >= 0 && R < s.length && s[L] == s[R]) {
L--;
R++;
}
return R - L - 1;
}
执行结果：
方法3(manacher算法)：
manacher算法很精妙，网上有很多解释来帮助理解，但这个算法个人理解起来很精妙，讲出来又是另外一回事，我就不做讲解了，大家自行理解吧，不明白的地方一起交流。时间复杂度是O(n)，是一种线性的计算方式，贴代码：
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function(s) {
let str = '#' + s.split('').join('#') + '#';
let len = str.length, maxRight = 0, p = [];
let maxIndex = 0, maxLenIndex = 0;
p[0] = 0;
for(let i = 1; i < len; i++) {
let j = 2*maxIndex -i;
if (i < maxRight) {
if (i + p[j] < maxRight) {
p[i] = p[j];
continue;
} else if(i + p[j] > maxRight) {
p[i] = maxRight - i;
continue;
}
}
let right = maxRight + 1;
let left = 2*i - maxRight - 1;
while(left >=0 && right < len && str[left]===str[right]) {
left --;
right ++;
}
p[i] = right-i-1;
maxIndex = i;
maxRight = p[i] + i;
if(p[i] > p[maxLenIndex]) {
maxLenIndex = i;
}
}
return str.substring(maxLenIndex-p[maxLenIndex]+1,maxLenIndex + p[maxLenIndex]).split('#').join('');
};
执行结果：
结语
以上是我对此题的解法，如果有小伙伴有更好的方式，或者非常有趣的思维方式，欢迎一起交流讨论。
希望此文能够解决大家工作和学习中的一些疑问，避免不必要的时间浪费，有不严谨的地方，也请大家批评指正，共同进步！
转载请注明出处，谢谢！