5. 最长回文子串 (中心向外扩展)
程序员文章站
2024-03-25 11:58:28
...
- 最长回文子串
给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1:
输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。
示例 2:
输入: “cbbd”
输出: “bb”
思路
首先分情况
- 第一种情况,只有一个字母,即长度为1,由于题目要求子串,所以原封不动返回
- 第二种情况,从中间向两侧进行扩展,eg abcbd 获得 bcb
- 第三种情况,也是从中间,但是没有中心点,eg abccbe 获得 bccb
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
if (s.length < 2) return s //情况1
let start = 0
let maxLength = 1 //初始化为1,防止出现ab这种长度为2的情况
//判断左右两边是否越界以及是否相等
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
if (right - left + 1 > maxLength) {
maxLength = right - left + 1
start = left
}
//继续向两侧扩展
left--
right++
}
}
//将每个都当成中心进行两侧扩展判断
for (let i = 0; i < s.length; i++) {
expandAroundCenter(i-1,i+1)//情况2
expandAroundCenter(i,i+1)//情况3
}
return s.substring(start , start+maxLength)
};
题目来自力扣
上一篇: jQuery慢慢啃之回调(十三)
下一篇: jQuery入门笔记之(四)动画效果