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;
}

思考

原来这个方法就叫做中心扩散法!

这题有几个值得注意的地方:

  1. 注意边界;
  2. 循环从中间开始,提前退出的概率会大些,可做优化;
  3. 中心扩散时注意 abba 这种可能性。我是通过引入 0.5 坐标解决,网上有人说 Manacher 算法(马拉车),通过塞 # 解决。异曲同工罢了。

评论

暂无评论