LeetCode刷题日志#4:最长回文子串 - 中心扩散法
文章目录
题目:传送门
类别:字符串
难度:中等
相关算法:中心扩散法
思路
回文就想对折一样,两边相同。所以先构造一个根据指定位置获取最长回文的函数,方法就是根据指定位置尽可能向两边蔓延,构成最长的回文。
然后需要一个循环,让每个数字都可能成为中心。
代码
/**
* @param {string} s
* @return {string}
*/
var longestPalindrome = function (s) {
const len = s.length;
const middleIndex = (len - 1) / 2;
let currRes = fold(middleIndex, s);
let flag = true;
let prevIndex = middleIndex - 0.5;
let nextIndex = middleIndex + 0.5;
while (flag) {
const idealLongest = prevIndex * 2 + 1;
const currResLen = currRes.nextIndex - currRes.prevIndex + 1;
if (currResLen < idealLongest) {
const prevRes = fold(prevIndex, s);
const prevResLen = prevRes.nextIndex - prevRes.prevIndex + 1;
if (prevResLen > currResLen) {
currRes = prevRes;
}
if (prevResLen >= idealLongest) {
flag = false;
} else {
const nextRes = fold(nextIndex, s);
const nextResLen = nextRes.nextIndex - nextRes.prevIndex + 1;
if (nextResLen > currResLen) {
currRes = nextRes;
}
if (nextResLen >= idealLongest) {
flag = false;
} else {
prevIndex -= 0.5;
nextIndex += 0.5;
}
}
} else {
flag = false;
}
}
return s.slice(currRes.prevIndex, currRes.nextIndex + 1);
};
// 判断对折
function fold(middleIndex, s) {
let str;
let flag = true;
let prevIndex = middleIndex;
let nextIndex = middleIndex;
if (!isInteger(middleIndex)) {
prevIndex += 0.5;
nextIndex -= 0.5;
}
while (prevIndex > 0 && nextIndex < s.length - 1) {
if (s[prevIndex - 1] === s[nextIndex + 1]) {
prevIndex -= 1;
nextIndex += 1;
} else {
return {
prevIndex,
nextIndex,
};
}
}
return {
prevIndex,
nextIndex,
};
}
function isInteger(number) {
return Math.floor(number) === number;
}
思考
原来这个方法就叫做中心扩散法!
这题有几个值得注意的地方:
- 注意边界;
- 循环从中间开始,提前退出的概率会大些,可做优化;
- 中心扩散时注意
abba这种可能性。我是通过引入 0.5 坐标解决,网上有人说 Manacher 算法(马拉车),通过塞#解决。异曲同工罢了。

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论