LeetCode 刷题之最长回文

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例：

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

输入: "cbbd"
输出: "bb"

一开始我的思路是，先假设整个字符串就是回文，从两头往中间检查，如果两头已经不匹配，那假设字符串长度 – 1 的子字符串是回文，此时这样的子字符串有俩。依旧两头往中间检查，如果找不到，子字符串的长度减 1。如果子字符串长度为原字符串长度 – n，那么这样的子字符串有 n + 1 个，一直找直到找出来回文为止。

我本来觉得这样的做法应当比暴力法还是要快很多的，但实际上运行的得分不怎么样。这里我也就略过这种算法的代码了。

后来我看了看官方答案，看起来最有效率的方法应该是 Manache 法（中文叫『马拉车』，快被笑死……）。算法的重点都在理解思路，我自己对 Manache 的思路理解如下。

还是用一个最简单的例子来说明，给出这样一个字符串 AAABAAC。

因为字符串回文长度为奇数和偶数时处理方式有点不同，为了统一处理，可以在字符串里面添加分隔符 | 来方便处理：|A|A|A|B|A|A|C|。

接下来记录每个字符为中心时的回文长度数：

|A|A|A|B|A|A|C|
01
  R

当我们遇到 A 时，出现了第一个回文，长度为 1（镜像部分长度而不是全部，后面一样），并且回文右边的 | （标记了 R）是目前发现出现回文最右边的边界。记录这些值的目的是什么呢？目前还看不出什么作用，但请先记住这个 R 的含义：出现回文时的最右位置。我们继续往下扫描：

|A|A|A|B|A|A|C|
012
    R

当我们遇到第二个 | 时，出现了更长的回文，同时 R 也扩展到了更右，再往下看的时候，我们就能发现 R 的妙用了。

目前我们统计到每个位置的回文长度数，都是自己对比出来的，但实际上，由于回文自己本身的特点，如果 R 已经是字符串的最右边界，那回文中心 A 后面的数我们都不用统计了，因为它们也应该是对称的，我们可以管回文中心叫做『镜』：

|A|A|A|B|A|A|C|
0121
    R

但 R 并不是『最右』，如果回文后面有某个字符，它的镜像回文统计长度，加上它自己本身的位置已经等于 R 这个位置了，那么我们可以尝试将 R 往右再推进试试，比如上面第二个 A，即可以将 R 往后推一格，此时镜也变成了第二个 A：

|A|A|A|B|A|A|C|
0123
      R

我们继续往下统计。第三个 | 相对于新的镜的『像』，统计的结果为 2，但实际上第三个 | 的位置往后移动 2，又再 R 上，所以 R 是否还能往后推，是还需要验证的，但我们只需要从 R 的位置开始往后校验即可：

|A|A|A|B|A|A|C|
01232
      R

结果发现 R 并没有往后推进。我们继续往下检查。实际上，我们最关心的事情，就是 R 能不能再往后推进：

|A|A|A|B|A|A|C|
01232105
            R

遇到 B 之后，R 被大大往后推进了，镜也变成了 B，我们按照上面的方法，继续往下检查，接下来要检查的 | 的『镜像』，回文长度为 0，本身往后移动 0 个位置不会超过 R，所以它的回文长度肯定是 0；再接下来的 A ，『镜像』回文长度是 1，但它本身往后 1 个位置也没超过 R，同理它的回文长度就是 1

|A|A|A|B|A|A|C|
0123210501
            R

接下来的 | 我们得到镜像回文长度为 2，它往后移动 2 个位置正好是 R，所以我们尝试把 R 往后推，结果是没有推动，所以它的回文长度还是 2。

我们可以继续利用马拉车尝试将 R 拉更远，这里有一个聊胜于无的小优化，目前回文最长到 5，实际上从刚刚统计过的 | 开始，它到字符串结束正好是 5，所以可以直接停止统计了。

我们再回过头来看看整个过程，可以发现，Manache 算法充分利用了回文的特点，一个长度为 n 的字符串，平均每个字符实际只对比了一次，所以它的复杂度为 O(n)。

说完了思路，再来看看边界条件。假设我们要检查的点是 i

1. 如果 i 正好踩在 R 这个位置，甚至超过 R，那显然要尝试将 R 推远
2. 如果 i 的位置往后移动它镜像 i0 的最大回文数已经大于 R，则 i 的最大回文数应当是 R 到 i 的距离，并且也需要将 R 推远
3. 如果 i 的位置往后移动它镜像 i0 的最大回文数不大于 R，则 i 的最大回文数跟 i0 位置是一样的，R 也不需要推进

综合上面的所有分析，代码如下

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function(s) {
    let a = [0, 1];
    let m = 1;
    let r = 2;
    let i = 1;

    let max = 1;
    let imax = 1;

    let len2 = s.length * 2 + 1;
    while (i < len2 - 1) {
        ++i;
        if (i + max > len2) {
            break;
        }

        if (i < r) {
            j = m + m - i;
            if (i + a[j] < r) {
                a[i] = a[j];

                continue;
            }
        }

        const d = Math.max(r - i + 1, 1);
        let il = i - d;
        let ir = i + d;

        while (ir < len2 && il >= 0) {
            if (il % 2 && s[(il - 1) / 2] !== s[(ir - 1) / 2]) {
                break;
            }

            r = ir;
            m = i;
            ++ir;
            --il;
        }

        a[i] = r - i;
        if (max < a[i]) {
            max = a[i];
            imax = i;
        }
    }

    return s.substr(((imax - a[imax]) / 2) | 0, max);
};

本来是写的 PHP 版本，遗憾的是，LeetCode 不知为何，PHP 代码无法通过测试，但实际上，即使是在 LeetCode 自己的测试功能里试运行，报错的示例也是能通过的为了通过测试，我换成了 JavaScript 版本。

后来我发现原来跟使用了 static 关键字有关，修改之后 PHP 版也可以运行。

class Solution {

    /**
     * @param String $s
     * @return String
     */
    function longestPalindrome($s) {
        $len = strlen($s);
        if ($len < 2) {
            return $s;
        }

        $a = [0, 1];
        $m = 1;
        $r = 2;
        $i = 1;
        $max = 1;
        $imax = 1;

        $len2 = $len * 2 + 1;
        while ($i < $len2 - 1) {
            ++$i;
            if ($i < $r) {
                $j = $m + $m - $i;
                if ($i + $a[$j] < $r) {
                    $a[$i] = $a[$j];

                    continue;
                }
            }

            $d = max($r - $i + 1, 1);
            $il = $i - $d;
            $ir = $i + $d;

            while ($ir < $len2 && $il >= 0) {
                if ($il % 2 && $s[($il - 1) / 2] !== $s[($ir - 1) / 2]) {
                    break;
                }

                $r = $ir;
                $m = $i;
                ++$ir;
                --$il;
            }

            $a[$i] = $r - $i;
            if ($max < $a[$i]) {
                $max = $a[$i];
                $imax = $i;
            }
        }

        return substr($s, intval(($imax - $a[$imax]) / 2), $max);
    }
}

再说说关于其他解法的理解。

动态规划

动态规划的核心是：将一个大问题，分解成更好思考的若干小问题。以最长回文为例，判断一个子字符串（假设为给定字符串的位置 i 到 j）是不是回文，可以分拆为判断从位置 i + 1 到 j – 1 是不是回文，以及 i 和 j 上的字符是否相同共同判断；可能大家已经看出来问题的拆分也成了一个套娃问题，最终会让 i 和 j 变成同一个位置，或者 i 和 j 相邻，此时问题就不能再拆了。另外为了提高运行速度，可以通过空间换时间的方式，将判断过的结果记录下来，形成一张表，因为当 i 和 j 相等的时候，一定是回文，对于一个总长度为 3 的字符串，表可以先这么初始化：

	0	1	2
0	true
1		true
2			true

对于 ABB 这个字符串，按照刚才所说的做法，最终会行成下面这张表：

	0 – A	1 – B	2 – B
0 – A	1. true	2. false	3. false
1 – B		1. true	2. true
2 – B			1. true

进行到第二轮，也就是子字符为两个长度时，发现当 i 为 1, j 为 2 时，有最长的回文；进行到第三轮时，发现无法再找到回文，程序结束。

事实上，就算字符总长度再长一点，如果在之前的某一轮已经无法找到回文，按我们上面对回文问题的拆分，后面的轮次都没有必要进行了。

中心扩展

这个方法我觉得可能没有必要再多解释，因为 Manache 方法就是一个优化后的中心扩展方法。

LeetCode 刷题之最长回文 by Chris Yue is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.