最长回文子串

[muxfe]

最长回文子串

最近在 leetcode 上刷算法题，重温一下 ACM 和 javascript 练手，发现了一道有趣的题目，最长回文子串。

开始的想法是反转字符串然后找出最大公共子串（LCS），但是 TLE 了。觉得可能是 js 本身效率太低，然后找了 leetcode 上别人写的算法分析，发现反转后找 LCS 是错误的，而且分析写得非常好，觉得应该好好学习下，记录在此。

回文

回文字符串就是指无论从那个方向读都是一样的，如'aba'就是一个简单的回文串。

开始的想法是先将字符串反转，然后找出它们的最长公共子串，即是要找最长回文串。

然而这是错误的！！！

比如 'abadfcdaba' 反转后是 'abadcfdaba'，它们的 LCS 是 'abad'，这显然不是一个回文串。

而它存在的原因就是原字符串中出现了两个一样的回文串，且有额外相同的部分分别出现在这两个回文串的前后。导致反转后的字符串除了回文部分相同外，还有非回文串也相同。

下面介绍几种不同的方法来计算 LPS。

暴力搜索

最简单的办法是找出字符串中的所有子串，判断其是否为回文串，然后记录下其中最大的回文子串即可。

暴搜无例外的话效率都很低，这个算法是 O(N^3) 的。首先找出所有子串 是 O(N^2) 的，然后判断其是否为回文是 O(N) 的。

var longestPalindrome_bf = function(s) {
  if (!s) return '';
  var longest = s[0], str, i, j, len;
  var isPalindrom = function (left, right) {
    while (left < right && s[left] === s[right]) {
      left++;
      right--;
    }
    return left >= right;
  }
  for (len = 2; len <= s.length; len++) {
    for (i = 0; i < s.length; i++) {
      j = i + len - 1;
      if (isPalindrom(i, j)) {
        str = s.slice(i, j + 1);
        if (longest.length < str.length) longest = str;
      }
    }
  }
  return longest;
}

动态规划

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;

算法实现如下：

var longestPalindrome_dp = function(s) {
  var i, j, len;
  // isPalindrom[i][j] represent s[i..j] is a parlindrom string or not.
  var isPalindrom = new Array(s.length);
  for (i = 0; i < s.length; i++) {
    isPalindrom[i] = new Array(s.length).fill(false);
  }
  var maxLen = 1, longestBegin = 0;
  // initialize
  for (i = 0; i < s.length; i++) {
    isPalindrom[i][i] = true;
    if (i < s.length - 1 && s[i] === s[i + 1]) {
      isPalindrom[i][i + 1] = true;
      maxLen = 2;
      longestBegin = i;
    }
  }
  // compute
  for (len = 3; len <= s.length; len++) {
    for (i = 0; i < s.length; i++) {
      j = len + i - 1;
      if (s[i] === s[j] && isPalindrom[i + 1][j - 1]) {
        isPalindrom[i][j] = true;
        maxLen = len;
        longestBegin = i;
      }
    }
  }
  return s.slice(longestBegin, longestBegin + maxLen);
}

这个实现在 leetcode 上 TLE 了。几乎跟暴搜一样慢。

ps. 我觉得跟 js 的数组对象有关。在 js 中处理二维数组比静态语言处理要慢的多。

继续优化

降低空间复杂度

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

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

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

实现如下：

var longestPalindrome_enum = function(s) {
  if (!s) return '';
  var longest = s[0];
  var expandAroundCenter = function (left, right) {
    while (left >= 0 && right < s.length && s[left] === s[right]) {
      left--;
      right++;
    }
    return s.slice(left + 1, right);
  }
  for (var i = 0; i < s.length; i++) {
    // 奇数
    var odd = expandAroundCenter(i, i);
    if (odd.length > longest.length) longest = odd;
    // 偶数
    var even = expandAroundCenter(i, i + 1);
    if (longest.length < even.length) longest = even;
  }
  return longest;
}

这个实现在 leetcode 上 AC 了，用了 236ms。

降低时间复杂度

相比降低空间复杂度，降低时间复杂度要难得多。这里有一个 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。

js 实现：

var longestPalindrome_manacher = function(s) {
  s = '^#' + s.split('').join('#') + '#$';
  var radius = new Array(s.length).fill(0);
  var C = 0, centerIndex = 0, maxRight = 0, maxLen = 0;

  for (var i = 1; i < s.length - 1; i++) {
    // 计算初始回文半径, i' = 2 * C - i
    radius[i] = (maxRight > i) ? Math.min(maxRight - i, radius[2 * C - i]) : 0;
    // 扩展半径
    while (s[i + 1 + radius[i]] && s[i - 1 - radius[i]] && s[i + 1 + radius[i]] === s[i - 1 - radius[i]]) radius[i]++;
    // 更新当前搜索的最大右边界和位置
    if (i + radius[i] > maxRight) {
      C = i;
      maxRight = i + radius[i];
    }
    // 更新最大回文串长度及位置
    if (maxLen < radius[i]) {
      maxLen = radius[i];
      centerIndex = i;
    }
  }

  return s.slice((centerIndex - maxLen), (centerIndex + maxLen + 1)).split('#').join('');
};

算法效果很好，在 leetcode 上运行时间是 160ms。

以上。

有用的链接

• Longest Palindromic Substring Part I
• Longest Palindromic Substring Part II
• Wiki:Longest palindromic substring
• Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串