暴力枚举法

思路

暴力解法虽然时间复杂度高，但是思路清晰、编写简单，因为编写的正确性高，完全可以使用暴力匹配算法检验我们编写的算法的正确性。

代码

复制
1var longestPalindrome_bf = function(s) {
2  if (!s) return '';
3  var longest = s[0], str, i, j, len;
4  var isPalindrom = function (left, right) {
5    while (left < right && s[left] === s[right]) {
6      left++;
7      right--;
8    }
9    return left >= right;
10  }
11  for (len = 2; len <= s.length; len++) {
12    for (i = 0; i < s.length; i++) {
13      j = i + len - 1;
14      if (isPalindrom(i, j)) {
15        str = s.slice(i, j + 1);
16        if (longest.length < str.length) longest = str;
17      }
18    }
19  }
20  return longest;
21}

复杂度

• 时间复杂度O(n^3)
• 空间复杂度O(1)

中心扩散法

思路

暴力法时间复杂度比较高，除此之外，还容易想到的是枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。

遍历原字符串，每个字符或每两个字符中间，都可能被当成回文子串的中心，利用回文串的中心对称的特点，尽量往两边扩散，获取最大的“扩散面积”

因此，中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。

枚举“中心位置”时间复杂度为 O(n) ，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(n) ，因此时间复杂度可以降到 O(n^2)。

在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。

• 奇数回文串的“中心”是一个具体的字符，例如：回文串 "aba" 的中心是字符 "a"；
• 偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串 "abba" 的中心是两个 "b" 中间的那个“空隙”。

代码

复制
1/**
2* @param {string} s
3* @return {string}
4*/
5var longestPalindrome = function (s) {
6    if (!s) return ''
7    if (s.length === 1) return s;
8    if (s.length === 2) return s[0] === s[1] ? s : s[1];
9    let maxStr = '',
10        len = s.length;
11    for (let i = 0; i < len; i++) {
12        let even = '', // 定义偶数中心回文
13            odd = ''; // 定义奇数中心回文
14        if (s[i] === s[i + 1]) { // 若是偶数中心回文
15            let evenIndex = center(s, i - 1, i + 2); // 比较中心的前一项和后一项
16            even = s.slice(evenIndex.left, evenIndex.right)
17        }
18        let oddIndex = center(s, i - 1, i + 1); // 奇数中心回文
19        odd = s.slice(oddIndex.left, oddIndex.right);
20        let longer = even.length > odd.length ? even : odd; // 比较奇、偶
21        maxStr = maxStr.length > longer.length ? maxStr : longer
22    }
23    return maxStr
24}
25// 中心扩展
26function center(s, left, right) {
27    let len = s.length;
28    while (left >= 0 && right < len && s[left] === s[right]) {
29        left--;
30        right++;
31    }
32    return { left: left + 1, right: right }
33}

动态规划

DP可能是解这个问题的一个好方法，然而算法复杂度依然是 O(N^2) 的，而且空间复杂度也是 O(N^2)。

我们假设用 P[i][j] 来表示 s[i..j] 是否是一个回文子串。

它的计算公式长这样：

P[i][j] = s[i] === s[j] && P[i + 1][j - 1] ? true : false;

复制
1var longestPalindrome_dp = function(s) {
2  var i, j, len;
3  // isPalindrom[i][j] represent s[i..j] is a parlindrom string or not.
4  var isPalindrom = new Array(s.length);
5  for (i = 0; i < s.length; i++) {
6    isPalindrom[i] = new Array(s.length).fill(false);
7  }
8  var maxLen = 1, longestBegin = 0;
9  // initialize
10  for (i = 0; i < s.length; i++) {
11    isPalindrom[i][i] = true;
12    if (i < s.length - 1 && s[i] === s[i + 1]) {
13      isPalindrom[i][i + 1] = true;
14      maxLen = 2;
15      longestBegin = i;
16    }
17  }
18  // compute
19  for (len = 3; len <= s.length; len++) {
20    for (i = 0; i < s.length; i++) {
21      j = len + i - 1;
22      if (s[i] === s[j] && isPalindrom[i + 1][j - 1]) {
23        isPalindrom[i][j] = true;
24        maxLen = len;
25        longestBegin = i;
26      }
27    }
28  }
29  return s.slice(longestBegin, longestBegin + maxLen);
30}
31

动态规划 2

思路

DP 的空间复杂度是 O(N^2) 的，主要用来保存二维数组 P[i][j]，而且只用了一半。

我们可以把空间复杂度降到 O(1)，只存找到的最长回文串即可。枚举轴心位置，并进行扩展。如果是回文，则轴心两边的字符应该对称相等。

需要考虑到长度奇偶情况的不同，如果是奇数长度，轴心就是一个字符；如果是偶数长度，轴心则不在字符串中

实现

复制
1var longestPalindrome_enum = function(s) {
2  if (!s) return '';
3  var longest = s[0];
4  var expandAroundCenter = function (left, right) {
5    while (left >= 0 && right < s.length && s[left] === s[right]) {
6      left--;
7      right++;
8    }
9    return s.slice(left + 1, right);
10  }
11  for (var i = 0; i < s.length; i++) {
12    // 奇数
13    var odd = expandAroundCenter(i, i);
14    if (odd.length > longest.length) longest = odd;
15    // 偶数
16    var even = expandAroundCenter(i, i + 1);
17    if (longest.length < even.length) longest = even;
18  }
19  return longest;
20}
21

Manacher 算法

相比降低空间复杂度，降低时间复杂度要难得多。这里有一个 O(N) 时间复杂度的算法，叫做 Manacher 算法。

能够从 O(N^2) 降到 O(N)，这个算法很巧妙。它首先解决了长度奇偶不同的问题。

通过向字符串中加入一些特殊字符来使长度均为奇数。特殊字符即为原字符串的字符集中没有的字符。如 'aba' 中插入 '#'，变成'#a#b#a#'。

然后提出了一个回文半径（P）的概念：

T = # a # b # a # a # b # a #
P = 0 1 0 3 0 1 6 1 0 3 0 1 0

它代表了以该字符为轴心的回文串对折后的长度。由于插入了特殊字符，如果最长回文字符串的长度为偶数，则轴心会出现在 '#' 上。

容易看出上面的例子中，最大回文子串的轴心就是 P 为 6 的字符。最大回文子串为 'abaaba' ，长度刚好为 6.

这显然不是巧合，接下来就是要计算 P，记下其最大值及对应下标，即可。目标时间复杂度 O(N)。当然，这个算法最难的部分，就是计算 P。

正常计算 P 的话，时间复杂度依然是 O(N^2)，但是如果利用回文串的对称特性，减少搜索，就可以将复杂度降至 O(N)。

计算 P 就是以每一个字符为轴心计算回文半径，也就是从每一个字符开始向两边搜索，那么右边必然会搜索到尚未遍历到的字符，如果我们记下最大能搜索到的右边界 R 。在后面的遍历搜索中，如果当前 T[i] 在边界内，即比最大右边界小，那么也就是在一个已搜索的回文子串中，假设 i' 是 i 对应当前最大 R 的轴心 C 的对称位置（即 T[i] == T[i']）， 可以做出下面的结论：

if P[i'] < R-i
then P[i] = P[i']
else P[i] >= P[i'] （需要进一步扩展搜索得出）

另一种情况，如果当前字符 T[i] 不在边界内，即我们不能得出任何结论，所以 P[i] = 0。

代码

复制
1var longestPalindrome_manacher = function(s) {
2  s = '^#' + s.split('').join('#') + '#$';
3  var radius = new Array(s.length).fill(0);
4  var C = 0, centerIndex = 0, maxRight = 0, maxLen = 0;
5
6  for (var i = 1; i < s.length - 1; i++) {
7    // 计算初始回文半径, i' = 2 * C - i
8    radius[i] = (maxRight > i) ? Math.min(maxRight - i, radius[2 * C - i]) : 0;
9    // 扩展半径
10    while (s[i + 1 + radius[i]] && s[i - 1 - radius[i]] && s[i + 1 + radius[i]] === s[i - 1 - radius[i]]) radius[i]++;
11    // 更新当前搜索的最大右边界和位置
12    if (i + radius[i] > maxRight) {
13      C = i;
14      maxRight = i + radius[i];
15    }
16    // 更新最大回文串长度及位置
17    if (maxLen < radius[i]) {
18      maxLen = radius[i];
19      centerIndex = i;
20    }
21  }
22
23  return s.slice((centerIndex - maxLen), (centerIndex + maxLen + 1)).split('#').join('');
24};
25