leetcode005最长回文子串

题目

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。

示例 1：

输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。


示例 2：

输入: "cbbd"
输出: "bb"


解题思路

暴力求解

大概思路是这样

let result = "";
for (let i = 0; i for (let j = i; j let sub = s.subStr(i, j+1);
if (checkSubstring(sub)) {
if (result.length result = sub;
}
}
}
}


两层循环套一个检查是否是回文串的函数，时间复杂度O(n3)

动态规划

最长的回文子串，去掉首尾肯定还是回文子串，于是可以从最短的回文子串开始一点点找到更长一点的回文子串

Array.prototype.setPush = function(val) {
if (!this.some(x => x === val)) {
this.push(val);
}
}
String.prototype.searchAll = function(val) {
let result = [];
for (let i = 0; i let index = this.indexOf(val, i);
if (index === -1) break;
else {
result.push(index);
i = index+1;
}
}
return result;
}
var lOngestPalindrome= function(s) {
if (s === "") return "";
const length = s.length;
let temp = [];
// 将1长度和2长度的回文子串全部取出
for (let i = 0; i temp.setPush(s[i]);
if (s[i] === s[i+1]) {
temp.setPush(s[i]+s[i]);
}
}
while (true) {
let tempTwo = [];
for (let i = 0; i let indexes = s.searchAll(temp[i]);
for (index of indexes) {
let a = index-1;
let b = index+temp[i].length;
if (s[a] === s[b] && s[a] !== undefined) {
tempTwo.setPush(s.slice(a, b+1));
}
}
}
if (tempTwo.length > 0) {
temp = tempTwo;
}
else {
let maybeMaxLength = temp[0].length;
if (temp.some(x => x.length !== maybeMaxLength)) {
for (x of temp) {
if (x.length > maybeMaxLength) return x;
}
}
return temp[0];
}
}
};


时间复杂度为O(n²)，空间复杂度为O(n²)。没什么问题，但是在js中超时了，leetcode中判定超时的例子实际运行时间大概在2s左右，应该是中间某些步骤需要优化

中心扩展算法

因为回文是对称的，可以找到一个中心向左右两边扩展。考虑奇数串和偶数串两种情况，可能有n + (n - 1)个中心

直接照搬解答中的java代码并做简单修改，通过了…

function expandAroundCenter(s, left, right) {
let L = left, R = right;
while(L >= 0 && R L--;
R++;
}
return R - L - 1;
}
/**
* @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 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);
};