3、最长回文子串

LeetCode 5. 最长回文子串

题目描述

给你一个字符串 s，找到 s 中最长的 回文

子串 。

示例 1：

输入：s = "babad" 输出："bab" 解释："aba" 同样是符合题意的答案。 示例 2：

输入：s = "cbbd" 输出："bb"

提示：

• 1 <= s.length <= 1000
• s 仅由数字和英文字母组成

思路

最长回文子串，可以分为两种情况：

1. 回文串的长度为奇数，如 "aba"
2. 回文串的长度为偶数，如 "abba"

我们用中心扩散法，从每个字符开始，向两边扩展，判断是否是回文串。

• 对于长度为奇数的回文串，中心点为 i，向两边扩展，如果 s[i] !== s[j] 则不是回文串，退出循环。
• 对于长度为偶数的回文串，中心点为 i 和 i+1，向两边扩展，如果 s[i] !== s[j] 则不是回文串，退出循环。

最后，返回最长的回文子串。

代码实现

var longestPalindrome = function (s) {
  if (s.length <= 1) return s;
  let left = 0;
  let right = 0;
  for (let i = 0; i < s.length - 1; i++) {
    // 回文有两种情况，一种是中间一个对称，如 aba，一种是两边对称，如 abba 所以要分别处理
    // 处理 aba 的情况
    getPalindrome(i, i);
    // 处理 abba 的情况
    getPalindrome(i, i + 1);
  }

  /**
   * @param {number} m 中心点左边
   * @param {number} n 中心点右边
   * @return {void}
   */
  function getPalindrome(m, n) {
    //处理边界情况， m 往左走，不能小于 0，n 往右走，不能大于 s.length - 1，m 不能大于 n
    while (m >= 0 && n < s.length && m <= n) {
      // 如果 s[m] !== s[n] 则不是回文，退出循环
      if (s[m] !== s[n]) {
        break;
      } else {
        // 否则 m 往左走，n 往右走，继续判断
        m--;
        n++;
      }
    }
    // 如果当前的回文子串长度大于之前的，则更新结果
    if (n - m > right - left) {
      left = m;
      right = n;
    }
  }
  // 左侧为什么 + 1，因为 while 循环等于 0 的时候，m 会变成 -1
  // 右侧则是最多 s.length - 1
  return s.slice(left + 1, right);
};

总结

回文的最好理解的方式就是中心扩散法，从每个字符或者是相邻两个字符开始扩散，判断是否是回文串。