LeetCode 刷题之最长回文

LeetCode 刷题之最长回文

Chris Yue No Comment
Posts

给定一个字符串 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 的字符串,表可以先这么初始化:

012
0true
1true
2true
横坐标是 i 纵座标是 j

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

0 – A1 – B2 – B
0 – A1. true2. false3. false
1 – B1. true2. true
2 – B1. true
结果前面的数字,表示子字符长度,也表示循环的轮次

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

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

中心扩展

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

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

微信赞赏码

写作累,服务器还越来越贵
求分担,祝愿好人一生平安
天使打赏人

发表评论

− 2 = 1