5.最长回文子串

最长回文子串

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

如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

示例 1：

输入：s = “babad”
输出：”bab”
解释：”aba” 同样是符合题意的答案。

示例 2：

输入：s = “cbbd”
输出：”bb”

提示：

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

解析

可以先尝试暴力求解，判断一个字符串是否为回文字符串可以通过反转字符串来解决

// 方法 1: 枚举法
求字符串全部子串，然后判断该子串是否为回文字符串。该方法时间复杂度为 $O(n^3)$，空间复杂度为 O(1)。

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  if (s.length < 2) return s;
  // 判断字符串是否为回文字符串
  function isPalindrome(str, i, j) {
    while (i < j) {
      if (str[i] !== str[j]) {
        return false;
      } else {
        i++;
        j--;
      }
    }
    return true;
  }

  let max = 0; // 当前最长回文子串的长度
  let start = 0;
  let end = 0;
  // 双重循环求全部子串
  for (let i = 0; i < s.length - 1; i++) {
    for (let j = i + 1; j < s.length; j++) {
      // 注意这里要先判断长度大于 max 再进行 isPalindrome 的判断，可以大大减少计算量
      if (j + 1 - i > max && isPalindrome(s, i, j)) {
        start = i;
        end = j;
        max = j + 1 - i;
      }
    }
  }
  // substring 截取数组下标开始位置和结束位置（不包含结束位置）
  return s.substring(start, end + 1);
};

方法2: 中心扩散法

中心扩散法思路是比较清晰的，遍历字符串的每个节点，然后由这个节点向两边扩散，扩散过程中求子串最大长度。