LeetCode最长回文子串JS实现

发布于:2021-07-26 23:16:26

最长回文子串

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


示例


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

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

思路
暴力求解

暴力求解,列举所有的子串,判断是否为回文串,保存最长的回文串。


复杂度
时间复杂度:




O


(



n


3



)



O(n^3)


O(n3)空间复杂度:




O


(


1


)



O(1)


O(1)
最长公共子串

把原来的字符串倒置了,然后找最长的公共子串。求出最长公共子串后,并不一定是回文串,还需要判断该字符串倒置前的下标和当前的字符串下标是不是匹配。


动态规划

基本思想:将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解(这部分与分治法相似)。与分治法不同的是,适合于用动态规划求解的问题,经分解得到的子问题往往不是互相独立的。若用分治法来解这类问题,则分解得到的子问题数目太多,有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案,而在需要时再找出已求得的答案,这样就可以避免大量的重复计算,节省时间。通常可以用一个表来记录所有已解的子问题的答案。不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划的基本思路。


采用动态规划求解的问题需要具有两个特性


最优子结构(Optimal Substructure):问题的一个最优解中所包含的子问题的解也是最优的。重叠子问题(Overlapping Subproblems):用递归算法对问题进行求解时,每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。

最长公共子序列(LCS)问题具有动态规划两个特性


动态规划解决最优化问题的一般步骤


    分析最优解的性质,并刻划其结构特征。递归地定义最优值。以自底向上的方式或自顶向下的记忆化方法计算出最优值。根据计算最优值时得到的信息,构造一个最优解。

解法

/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (s === "") return ""
let origin = s, reverse = s.split(').reverse().join(')
let len = s.length
let arr = []
let maxLen = 0, maxEnd = 0
for (let i = 0; i < len; i++) {
for (let j = len - 1; j >= 0; j--) {
if (origin[i] === reverse[j]) {
if (i == 0 || j == 0) {
arr[j] = 1
} else {
arr[j] = arr[j - 1] + 1
}
} else {
arr[j] = 0
}
if (arr[j] > maxLen) {
let beforeRev = len - 1 - j;
if (beforeRev + arr[j] - 1 == i) {
maxLen = arr[j];
maxEnd = i;
}
}
}
}
return s.substring(maxEnd - maxLen + 1, maxEnd + 1)
}

复杂度
时间复杂度:




O


(



n


2



)



O(n^2)


O(n2)空间复杂度:




O


(


n


)



O(n)


O(n)
扩展中心

我们知道回文串一定是对称的,所以我们可以每次循环选择一个中心,进行左右扩展,判断左右字符是否相等即可


由于存在奇数的字符串和偶数的字符串,所以我们需要从一个字符开始扩展,或者从两个字符之间开始扩展,所以总共有 n+n-1 个中心。


解法

/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (s === "") return ""
let start = 0, end = 0;
for (let i = 0; i < s.length; 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);
}

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;
}


复杂度
时间复杂度:




O


(



N


2



)



O(N^2)


O(N2)空间复杂度:




O


(


1


)



O(1)


O(1)
最优解:马拉车算法(Manacher’s Algorithm)
解法

/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
let T = preProcess(s);
let n = T.length;
let P = [];
let C = 0, R = 0;
for (let i = 1; i < n - 1; i++) {
let i_mirror = 2 * C - i;
if (R > i) {
P[i] = Math.min(R - i, P[i_mirror]);
} else {
P[i] = 0;
}

while (T.charAt(i + 1 + P[i]) == T.charAt(i - 1 - P[i])) {
P[i]++;
}

if (i + P[i] > R) {
C = i;
R = i + P[i];
}

}

let maxLen = 0;
let centerIndex = 0;
for (let i = 1; i < n - 1; i++) {
if (P[i] > maxLen) {
maxLen = P[i];
centerIndex = i;
}
}
let start = (centerIndex - maxLen) / 2;
return s.substring(start, start + maxLen);
}

function preProcess(s) {
let n = s.length;
if (n == 0) {
return "^$";
}
let ret = "^";
for (let i = 0; i < n; i++)
ret += "#" + s[i];
ret += "#$";
return ret;
}

复杂度
时间复杂度:




O


(


n


)



O(n)


O(n)空间复杂度:




O


(


n


)



O(n)


O(n)

相关推荐

最新更新

猜你喜欢