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

示例1：

输入：s = “babad” 输出：“bab” 或 “aba”

示例2：

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

提示：

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

动态规划法 - Dynamic Programming

微信截图_20220505214008.png
微信截图_20220505223046.png
时间复杂度：O(n^2)
空间复杂度：O(n^2)

  1. function longestPalindrome(s: string): string {
  2.     const len = s.length;
  3.     if (len < 2) {
  4.        return s; 
  5.     }
  6.     let maxLen = 1, start = 0;
  7.     // dp[i][j]表示s[i..j]是否是回文串
  8.     const dp: Array<Array<Boolean>> = new Array<Array<Boolean>>();
  9.     for(let i = 0; i < len; i++) {
  10.         dp[i] = [];
  11.         dp[i][i] = true; // 此行可忽略
  12.     }
  13.     const charArray: Array<String> = s.split('');
  14.     // 先枚举子串长度
  15.     for (let L = 2; L <= len; L++) {
  16.         // 枚举左边界，左边界的上限设定可以宽松些
  17.         for (let i = 0; i < len; i++) {
  18.             // 状态转移方程：dp[i][j] = (s[i] == s[j]) and dp[i+1][j-1]也是子串
  19.             // L和i确定右边界，边界条件：(j-1) - (i+1) + 1 < 2,s[i..j]的长度为2或3时，不用检查子串是否是回文
  20.             let j = L + i - 1;
  21.             // 处理越界
  22.             if (j >= len) {
  23.                 break;
  24.             }
  25.             if (charArray[i] != charArray[j]) {
  26.                 dp[i][j] = false; 
  27.             } else {
  28.                 if (j - i < 3) {
  29.                     dp[i][j] = true;  
  30.                 } else {
  31.                     dp[i][j] = dp[i+1][j-1]; 
  32.                 }
  33.             }
  34.              // 只要 dp[i][L] == true 成立，就表示子串 s[i..L] 是回文，此时记录回文长度和起始位置
  35.             if (dp[i][j] && j - i + 1 > maxLen) {
  36.                   maxLen = j - i + 1;
  37.                   start = i;
  38.              }
  39.         }
  40.     }
  41.     return s.substring(start, start + maxLen);
  42. };

中心扩展法

微信截图_20220505215119.png
注意奇偶差异。// 首先不能越界，其次两个元素要相等，然后m左移，n右移进行比较
时间复杂度：O(n^2)
空间复杂度：O(1)

function longestPalindrome(s: string): string {
    if (!s && s !== '0') {
      return '';
    }
    const len = s.length;
    if (len < 2) {
       return s; 
    }
    let start = 0, maxLen = 1;
    for(let i = 0; i < len; i++) {
        // 当回文子串为奇数时
        const oddLen = expandAroundCenter(s, i, i);
        // 当回文子串为偶数时
        const evenLen = expandAroundCenter(s, i, i+1);
        const curMaxLen = Math.max(oddLen, evenLen);
        if (curMaxLen > maxLen) {
            maxLen = curMaxLen;
            // 注意回文子串为偶数时，
            start = i - Math.floor((maxLen - 1)/2);
        }
    }
    return s.substring(start, start + maxLen);
};
// 返回回文串的长度
function expandAroundCenter(s: string, left: number, right: number): number {
    // 首先不能越界，其次两个元素要相等，然后left左移，right右移进行比较
    while (left >= 0 && right < s.length && s.charAt(left) === s.charAt(right)) {
        left--;
        right++;
    }

    return right - left - 1;
}

如果我们只在必要的字符处展开而不是在每个字符处展开，效率会不会快很多？

Manacher法

回文的左侧是其右侧的镜像。
新概念：臂长，表示中心扩展算法向外扩展的长度。如果一个位置的最大回文字符串长度为 2 * length + 1 ，其臂长为 length。
例如，考虑输入字符串“abacaba”。当它到达“c”时，Manacher 的算法将识别出以“c”之前的字母为中心的每个回文的长度。在“c”处，它运行一个循环来识别以“c”为中心的最大回文：“abacaba”。有了这些知识，“c”之后的所有内容看起来就像“c”之前的所有内容的反映。“c”之后的“a”与“c”之前的“a”具有相同的最长回文。类似地，“c”之后的“b”具有最长回文，其长度至少是以“c”之前的“b”为中心的最长回文的长度。有一些特殊情况需要考虑，但这个技巧大大加快了计算速度。

时间复杂度：O(n)
空间复杂度：O(n)

function longestPalindrome(s: string): string {
    if (!s && s !== '0') {
      return '';
    }
    // seperation，无需区分原字符串长度是奇数还是偶数
    const newStr = `#${s.split('').join('#')}#`;
    const newLen = newStr.length; // 2n+1
    let center = 0, radius = 0;    // 中心点，半径
    const palindromeRadii: Array<number> = new Array(newLen).fill(0);    // 在s中以每个位置为中心的最长回文的半径
    while(center < newLen) {
        const left = center - (radius+1), right = center + (radius+1);
        // 确定从Center-Radius开始到Center+Radius的最长回文
        while(left >= 0 && right < newLen && newStr.charAt(left) === newStr.charAt(right)) {
            radius++;  
        }
        // 将最长回文的半径保存到数组中
        palindromRadii[center] = radius;
        const oldCenter = center, oldRadius = radius;
        center++;
        radius = 0;
        while(center <= oldCenter + oldRadius) {
            const mirroredCenter = oldCenter - (center - oldCenter);
            const maxMirroredRadius = oldCenter + oldRadius - center;
            // 镜像中心的回文位于旧回文内部
            if (palindromeRadii[mirroredCenter] < maxMirroredRadius) {
                palindromeRadii[center] = palindromeRadii[mirroredCenter];
            } else if (palindromeRadii[mirroredCenter] > maxMirroredRadius) {    // 镜像中心的回文延伸至旧回文外部
                palindromeRadii[center] = maxMirroredRadius;
                center++;
            } else {    // 镜像中心的回文正好延伸至旧回文边界
                radius = maxMirroredRadius;
                break;
            }
        }
    }
    const maxLen = Math.max(...palindromeRadii);
    return s.substring((palindromeRadii.indexOf(maxLen) - maxLen)/2, maxLen);
};