网站接入服务单位名称,做柜子好的设计网站,三丰云做网站教程,十堰秦楚网官网题目描述
给定一个字符串 s#xff0c;找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1#xff1a;
输入: babad 输出: bab 注意: aba 也是一个有效答案。
示例 2#xff1a;
输入: cbbd 输出: 找到 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 i0; is.length; i) {for(let j i; j s.length; j) {m.push(s.slice(i, j1))}}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 i0; is.length; i) {for(let j i; j s.length; j) {if (s[i] ! s[j]) breaklet ele s.slice(i, j1)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-len1, end1)
}思路三中心拓展
遍历一遍字符串以每个字符为中心向两边判断是否为回文字符串
复杂度分析
时间复杂度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 i0; iformatSize; 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--jstep}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 i0; iformatSize; 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 算法
文章更新平台掘金、知乎。
