5. 最长回文子串

leetcode

题目

image.png

思路一 动态规划

dp[i][j]为true，字符串从i到j的子串为回文串，否则不是回文串。

当dp[i+1][j-1]为回文串时，且dp[i]与dp[j]相同，则dp[i][j]为回文串。

特殊情况：长度为0或1的字符皆为回文串，j-i<2。

复杂度

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

空间复杂度：O(n^2)

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  let res = '';
  let n = s.length;
  let dp = Array.from({ length: n }, () => new Array(n));
  // 这里i必须倒序遍历（后面要取dp[i+1]）
  for (let i = n - 1; i >= 0; i--) {
    for (let j = i; j < n; j++) {
      // 主要看这里
      dp[i][j] = (s[i] === s[j]) && (j - i < 2 || dp[i + 1][j - 1]);
      // 找最长
      if (dp[i][j] && (j - i + 1 > res.length)) res = s.substring(i, j + 1);
    }
  }
  return res;
};

思路二 中心扩展算法

先预处理字符串，每个字符之间都加入‘#’，然后首尾添加^$，保证字符串长度为奇数。

中心扩展思想：分别以每个字符为中心向外扩展，尝试出该中心的最长回文串的长度，最终得到最长回文串的中心（maxIdx）以及长度（max），最长回文串的开始下标（start）为（maxIdx-max）/2，结束下标（end）为 start + max。

复杂度

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

空间复杂度：O(1)

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/**
 * @param {string} s
 * @return {string}
 */
function findLongestPalindrome(str) {
  // 拼接字符串（拼接后字符个数为奇数个）
  let tempStr = `^#${str.split('').join('#')}#$`;
  let max = 0, maxIdx = 0;

  for (let i = 1; i < tempStr.length - 1; i++) {
    let n = 0
    // 中心扩展，计算第i元素的最长回文串的半径
    while (tempStr[i - n - 1] === tempStr[i + n + 1]) {
      n += 1;
    }

    // 取最大值
    if (n > max) {
      max = n;
      maxIdx = i;
    }
  }

  // 计算最长回文串的起始位置
  // Math.floor((最长回文中心点-最长回文长度) / 2)
  let start = (maxIdx - max) >> 1;
  let end = start + max;
  return str.slice(start, end);
}

思路三 马拉车算法

马拉车算法为中心扩展算法的优化版本，利用已知条件判断以当前字符为中心的回文串最小长度。

情况一

比如 ABADABA，以D为中心，左右两边都为ABA，已知下标为i=1的最长回文串为ABA，半径为1；下标为j=3的最长回文串为ABADABA，半径为3。那么i以j为中心的对称点，下标为z=5的最长回文子串也为ABA，半径为1。

情况二

上面是最理想的情况，再比如：DABADABAE，在左边加了D，右边加了E。下标为i=2处DABAD是回文串，半径为2，下标为j=4处ABADABA也是回文串，半径为3，那么那么i以j为中心的对称点，下标为z=6处 + i处回文串半径2 = 8，超出了j=4处回文串的右边界7。这个情况只能保守处理，虽然不能保证边界外的字符依然是回文串，但能保证边界内的是回文串，所以我们取一个 z到右边界的距离 和 i处回文串半径的最小值，然后再继续中心扩展。

复杂度

时间复杂度：O(n)

空间复杂度：O(n)

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {string} s
 * @return {string}
 */
function findLongestPalindrome(str) {
  // 拼接字符串（拼接后字符个数为奇数个）
  let tempStr = `^#${str.split('').join('#')}#$`;
  // 记录一个数组p，记录分别以每个字符为中心的最长回文串长度
  let p = new Array(tempStr.length).fill(0);
  let max = 0, maxIdx = 0;
  let center = 0, right = 0;

  for (let i = 1; i < tempStr.length - 1; i++) {
    // 马拉车优化1：设当前已知最长回文为a
    // 若i没超出a的右边界，那么i关于当前已知最长回文的中心点的对称点为i_mirror
    // 以i与i_mirror为中心的最长回文两者相关。
    // 设i_mirror为中心的最长回文半径为p[i_mirror]，若i+p[i_mirror]>right，则超出的部分在对应i-p[i_mirror]上不一定相等。
    // 所以这里以右边界取了最小值
    if (i < right) {
      p[i] = Math.min(right - i, p[center - (i - center)]);
    }

    // 中心扩展，计算第i元素的最长回文串的半径
    while (tempStr[i - p[i] - 1] === tempStr[i + p[i] + 1]) {
      p[i] += 1;
    }

    // 马拉车优化2：更新右边界，以及对应的回文串中心点。
    if (right < i + p[i]) {
      right = i + p[i];
      center = i;
    }

    // 取最大值
    if (p[i] > max) {
      max = p[i];
      maxIdx = i;
    }
  }

  // 计算最长回文串的起始位置
  // Math.floor((最长回文中心点-最长回文长度) / 2)
  let start = (maxIdx - max) >> 1;
  let end = start + max;
  return str.slice(start, end);
}