【算法题系列】LeetCode 5.最长回文子串｜JavaScript 5种思路实现

题目描述

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

示例 1：

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

示例 2：

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

题解

回文：指一个正读和反读都相同的字符串，例如，“aba” 是回文，而 “abc” 不是。

解决方案

思路一：暴力法

即通过双重遍历来获取目标字符串所有的子串，push 到一个数组里面，然后根据字符串长度排序，从最长字串开始循环校验，第一个为回文的子串就是我们要的结果

复杂度分析

• 时间复杂度：O(n^3)
• 空间复杂度：O(1)

/*** @param {string} s* @return {string}*/
var longestPalindrome = function(s) {let m = []let res = ''for(let i=0; i<s.length; i++) {for(let j = i; j < s.length; j++) {m.push(s.slice(i, j+1))}}m.sort(function(a,b){return b.length - a.length})for (let i of m) {if (i === i.split('').reverse().join('')) {res = ibreak;}}return res
}

上面代码在目标字符串长度过大的时候，会超出时间限制，远远超出O(n^2) 的理想时间复杂度，这是因为过多的for 循环，js 自带函数使用过多造成的，优化一下

var longestPalindrome = function(s) {let m = []let res = ''for(let i=0; i<s.length; i++) {for(let j = i; j < s.length; j++) {if (s[i] != s[j]) breaklet ele = s.slice(i, j+1)if (ele === ele.split('').reverse().join('') && ele.length > res.length) {res = ele}}}return res
}

看起来好多了，但是依然通不过Leecode 的测试，我觉得必须要把 slice split reverse join 这些函数都干掉才行，也可能 JS 语言效率确实慢一些

思路二：最长公共字串

反转 S，使之变成 S'。找到 S 和 S' 之间最长的公共子串，判断是否是回文

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(n^2)

/*** @param {string} s* @return {string}*/
var longestPalindrome = function(s) {let rs = s.split('').reverse().join('')let size = s.lengthlet len = 0let end = 0let a = new Array(size)for (let i = 0; i < size; i++) {a[i] = new Array()}for (let i = 0; i < size; i++) {for(let j = 0; j < size; j++) {if (s[i] === rs[j]) {if (i > 0 && j > 0) {a[i][j] = a[i-1][j-1] + 1} else {a[i][j] = 1}if(a[i][j] > len) {let beforeIndex = size - 1 - jif (beforeIndex + a[i][j] -1 == i) { len = a[i][j]end = i}}} else {a[i][j] = 0}}}return s.slice(end-len+1, end+1)
}

思路三：中心拓展

遍历一遍字符串，以每个字符为中心向两边判断，是否为回文字符串

复杂度分析

• 时间复杂度：O(n^2)
• 空间复杂度：O(1)

/*** @param {string} s* @return {string}*/
var longestPalindrome = function(s) {let size = s.lengthlet start = 0let len = 0 //字串长度// 奇数长度的回文字串for (let i = 0; i < size; i++) {let left = i - 1let right = i + 1while (left >= 0 && right < size && s[left] == s[right]) {left --right ++}if (right - left - 1 > len) {start = left +1len = right -left -1}}// 偶数长度的回文字串for (let i = 0; i < size; i++) {let left = ilet right = i + 1while (left >= 0 && right < size && s[left] == s[right]) {left--right++}if (right -left -1 > len) {start = left + 1len = right -left -1}}return s.slice(start, start + len)
}

思路四：动态规划

思路五：Manacher 算法

manacher 算法涉及中心拓展法、动态规划，是manacher 1975年发明出来用来解决最长回文子串的线性算法

// 第一步
var longestPalindrome = function(s) {let size = s.lengthif (size < 2) {return s}let str = addBoundaries(s, '#')let formatSize = 2 * size +1let maxSize = 1let start = 0for (let i=0; i<formatSize; i++) {let curSize = centerSpread(str, i)if (curSize > maxSize) {maxSize = curSizestart = (i - maxSize)/2}}return s.slice(start, start + maxSize)
}// 处理原字符串
var addBoundaries = function(s, divide) {let size = s.lengthif (size === 0) {return ''}if (s.indexOf(divide) != -1) {throw new Error('参数错误，您传递的分割字符，在输入字符串中存在！')}return divide + s.split('').join(divide) + divide
}// 辅助数组
var centerSpread = function(s, center) {// left = right 的时候，此时回文中心是一个空隙，回文串的长度是奇数// right = left + 1 的时候，此时回文中心是任意一个字符，回文串的长度是偶数let len = s.lengthlet i = center - 1let j = center + 1let step = 0while (i >= 0 && j < len && s.charAt(i) == s.charAt(j)) {i--j++step++}return step
}
longestPalindrome('ababadfglldf;hk;lhk')

manacher 算法的工作，就是对上面代码中的辅助数组 p 进行优化，使时间复杂度的降到O(n^2)

// 完整
var longestPalindrome = function(s) {let size = s.lengthif (size < 2) {return s}let str = addBoundaries(s, '#')let formatSize = 2 * size +1let p = new Array(formatSize).fill(0)let maxRight = 0let center = 0let maxSize = 1let start = 0for (let i=0; i<formatSize; i++) {if (i < maxRight) {let mirror = 2 * center - i;// Manacher 算法的核心p[i] = Math.min(maxRight - i, p[mirror]);}// 下一次尝试扩散的左右起点，能扩散的步数直接加到 p[i] 中let left = i - (1 + p[i]);let right = i + (1 + p[i]);// left >= 0 && right < formatSize 保证不越界// str.charAt(left) == str.charAt(right) 表示可以扩散 1 次while (left >= 0 && right < formatSize && str.charAt(left) == str.charAt(right)) {p[i]++;left--;right++;}// 根据 maxRight 的定义，它是遍历过的 i 的 i + p[i] 的最大者// 如果 maxRight 的值越大，进入上面 i < maxRight 的判断的可能性就越大，这样就可以重复利用之前判断过的回文信息了if (i + p[i] > maxRight) {// maxRight 和 center 需要同时更新maxRight = i + p[i];center = i;}if (p[i] > maxSize) {// 记录最长回文子串的长度和相应它在原始字符串中的起点maxSize = p[i];start = (i - maxSize) / 2;}}return s.slice(start, start + maxSize)
}var addBoundaries = function(s, divide) {let size = s.lengthif (size === 0) {return ''}if (s.indexOf(divide) != -1) {throw new Error('参数错误，您传递的分割字符，在输入字符串中存在！')}return divide + s.split('').join(divide) + divide
}
longestPalindrome('babb')

参考链接：manacher 算法

文章更新平台：掘金、知乎。