[5] 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入："babad"

输出："bab"

注意："aba" 也是一个有效答案。

示例 2：

输入："cbbd"

输出："bb"

求最长回文子串，这是一道非常经典的字符串问题，需要重点理解。

这道题提供两个解题思路。

动态规划法

一般遇到求极值的问题时，就是动态规划解题的时机了。

如果用动态规划来解的话，我们需要推导出这道题的状态转移方程。字符串涉及到对字符的比对求极值的问题，我们通常从二维数组开始考虑，dp[i][j] 用于表示从 i 至 j 中截取的一段子串满足题意的可能情况。

在这道题中，我们可以设dp[i][j]表示 s 中从 i 到 j 是否可以形成回文。

之后我们来分析规律的推导，通过回文的定义我们可以得出以下三点结论：

1. 当j - i = 0时，即表示当前子串为单个字符，那么一定是回文。
2. 当j - i = 1时，表示当前子串为临近的两个字符，那么只有他们相等时，该子串才为回文。
3. 其余情况下，当首尾两个字符相等，且去除了首尾字符后的字符串为回文时，当前子串为回文。

基于第三点，我们可以得出状态转移方程：dp[i][j] = s[i] === s[j] && dp[i+1][j-1]。

这里需要着重注意的是，二维数组的遍历顺序。

因为 dp[i][j] 依赖 dp[i+1][j-1]，即左下角的值来做判断。并且在对角线位置，即 i = j 时，结果一定为 true。因此，我们只需要遍历二维数组的右上半部分，遵循从下到上，从左到右的顺序来遍历二维数组。

最后，题目需要我们得出最长的子串，我们只需要用一个变量记录最长子串，在遍历到dp[i][j]为 true 的时候比对下此时生成的子串是否比当前记录值长，若是则更新即可。

function longestPalindrome(s: string): string {
  let res = '';
  const len = s.length;
  // 二维数组，dp[i][j] 表示 s 中 从 i 到 j 的子串是否为回文串
  const dp: number[][] = Array(len)
    .fill(0)
    .map(x => Array(len).fill(0));

  // 注意遍历顺序！
  // 这里需要用 i 遍历 s，找到以 i 开头的子串是否为回文串，因此 i 的遍历顺序为倒序
  for (let i = len - 1; i >= 0; i--) {
    for (let j = i; j < len; j++) {
      // 1. 当`j - i = 0`时，即表示当前子串为单个字符，那么一定是回文。
      // 2. 当`j - i = 1`时，表示当前子串为临近的两个字符，那么只有他们相等时，该子串才为回文。
      // 3. 其余情况下，当首尾两个字符相等，且去除了首尾字符后的字符串为回文时，当前子串为回文。
      if (i === j) {
        dp[i][j] = 1;
      } else if (j - i === 1) {
        dp[i][j] = s[i] === s[j] ? 1 : 0;
      } else {
        dp[i][j] = s[i] === s[j] && dp[i + 1][j - 1];
      }

      // 当前子串为回文，且长度大于当前 res 时，更新结果
      if (dp[i][j] && j - i + 1 > res.length) {
        res = s.substring(i, j + 1);
      }
    }
  }
  return res;
}

当然，我们还可以优化下它的空间复杂度。因为我们在遍历时，发现dp[i][j]只与其左下角的值有关，因此我们可以用一个一维数组，每次只存储下dp[i][j]的下一行记录也能达到一样的效果。

这里需要注意的是，由于dp[j]依赖之前下一行的dp[j-1]，因此需要将 j 的遍历顺序反过来，防止前一次遍历的记录被覆盖。

var longestPalindrome = function(s) {
  let res = '';
  const dp = new Array(s.length).fill(0);
  for (let i = s.length - 1; i >= 0; i--) {
    for (let j =  s.length - 1; j >= 0; j--) {
      if (i === j) {
        dp[j] = 1;
      } else if (j - i === 1) {
        dp[j] = s[i] === s[j] ? 1 : 0;
      } else {
        dp[j] = s[i] === s[j] && dp[j - 1];
      }
      if (dp[j] && j - i + 1 >= res.length) {
        res = s.substring(i, j + 1);
      }
    }
  }
  return res;
};

双指针法

其实我们还有另一种方法来思考这个问题。

所谓回文就是指以某个字符为中心，不断向左右两边扩充相同字符，这样形成的字符串一定是回文。

那么我们只要遍历每一个字符，找出以这个字符为中心，向两边能扩散出的最长字符串并比较即可。

注意这里回文串可能有两种情况：回文串为奇数时，中心字符为1个。回文串为偶数时，中心字符为相等的两个字符，需要分别来运算。

function longestPalindrome(s: string): string {
  let res = '';
  const len = s.length;

  // 双指针思路，使用 i 遍历 s，找出以 s[i] 为中心字符，像两边扩散的最长回文串，并更新答案
  for (let i = 0; i < s.length; i++) {
    // 找到以 s[i] 为中心字符的回文串
    const subString1 = longestSubpalindrome(i, i);
    // 找到以 s[i] 与 s[i+1] 为中心字符的回文串
    const subString2 = longestSubpalindrome(i, i + 1);

    // 更新最长回文子串
    const temp = subString1.length > subString2.length ? subString1 : subString2;
    res = res.length < temp.length ? temp : res;
  }

  return res;

  function longestSubpalindrome(left: number, right: number) {
    // 防止越界
    while (left >= 0 && right < len && s[left] === s[right]) {
      left -= 1;
      right += 1;
    }
    return s.substring(left + 1, right);
  }
}