给你一个字符串 s,找到 s 中最长的回文子串。
s = “babad”
“bab”
“aba” 同样是符合题意的答案。
中心扩展法 由子串的中心向两边展开,也就是模拟双指针
例如:babad
// 中心扩展法
const longestPalindrome = (s) => {
let max = 0 //当前最大回文串的长度
let start = -1 // 当前最大回文串的起始索引
let len = s.length // s的长度
for (let i = 0; i < len; i++) {
// 遍历S
let now = 1 // 当前回文串的长度
let left = i - 1 // 左侧开始遍历的指针
while (s[i + 1] === s[i]) {
//如果当前字符后边的字符都一样,当前长度 +1,s遍历指针向后推
now++
i++
}
let right = i + 1 //获取到右侧开始遍历的指针
while (s[left] === s[right] && s[left] != undefined) {
// 从连续字符串两端开始向两侧拓展,直到越界或者不一致,一致的直接累积到当前长度中,修改左右指针
now += 2
left--
right++
}
if (now > max) {
// 判断与之前的最大的对比,更新的当前最大的回文串起始索引
max = now
start = left + 1
}
}
return s.slice(start, start + max) // 通过最大长度和起始索引,获取需要的字符串
}
let s = 'babad'
console.log(longestPalindrome(s))