5 Longest Palindromic Substring

题目

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.
Example 2:

Input: "cbbd"
Output: "bb"

解题思路

从左向右依次遍历字符串.
以当前字符(假设回文数为基数长度)或当前字符和下一个字符(假设回文数为偶数长度)为回文数中心, 向左右两侧搜索.

时间复杂度 $O(n^2)$

代码

const longestPalindrome = function(s) {
  const len = s.length;

  // 字符串长度为0或1时,回文数就是整个字符串本身
  if (len <= 1) {
    return s;
  }

  let maxPalStrLeft = 0,
    maxPalStrRight = 0;

  const expandAroundCenter = (left, right) => {
    // 当两字符相同且不超出数组长度时, 继续判断下一对字母是否相同  
    // 直到超出数组长度/左右的字母不同时,跳出循环  
    while (left >= 0 && right < len && s[left] === s[right]) {
      left--;
      right++;
    }
    // 还原回文的左右字符位置
    // 在大多数情况下, while 至少被执行了1次
    // 唯一的例外是expandAroundCenter(i, i + 1) i = len - 1 时(即最后一个字符), i + 1 越界直接跳过了 while 循环

    left++;
    right--;

    // 如果当前的回文数长度大于之前的最大回文数, 则储存当前的回文数
    if (right - left > maxPalStrRight - maxPalStrLeft) {
      maxPalStrLeft = left;
      maxPalStrRight = right;
    }
  };

  for (let i = 0; i < len; i++) {
    expandAroundCenter(i, i); // 假设有基数长度的回文数,即回文数中心点有一个字母
    expandAroundCenter(i, i + 1); // 假设有偶数长度的回文数, 即回文数中心点有两个字母,且这两个字母相同
  }

  return s.slice(maxPalStrLeft, maxPalStrRight + 1);
};

// test
console.log(longestPalindrome('babad'));
console.log(longestPalindrome('cbbd'));
console.log(longestPalindrome('bacd'));
console.log(longestPalindrome('a'));
console.log(longestPalindrome('bananas'));
console.log(longestPalindrome('aaabaaaa'));
console.log(longestPalindrome('ab'));

边界情况:
以字符串 ab 为例, 调用 expandAroundCenter(i, i + 1), 即expandAroundCenter(1, 2)

// len = 2
const expandAroundCenter = (left, right) => {
    // 应为right < len 不成立, while 循环被直接跳过了
    while (left >= 0 && right < len && s[left] === s[right]) {
      left--;
      right++;
    }
    // 此时 left 的值为 1, right 的值为 2
    left++;
    right--;
    // 此时 left 的值为 2, right 的值为 1
    
    // right - left = 1 - 2 = -1, 而 maxPalStrRight - maxPalStrLeft的最小值是 0  
    // 此时 if 里的内容不可能被执行
    if (right - left > maxPalStrRight - maxPalStrLeft) {
      maxPalStrLeft = left;
      maxPalStrRight = right;
    }
  };
expandAroundCenter(1, 2)