LeetCode Day 5

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案，但我们只输出第一个满足条件的字符串。

思路

中心扩展法：这段说明来自LeetCode官网，事实上，只需使用恒定的空间，我们就可以在 O(n^2)的时间内解决这个问题。我们观察到回文中心的两侧互为镜像。因此，回文可以从它的中心展开，并且只有2n−1个这样的中心。你可能会问，为什么会是2n - 1个，而不是n个中心？原因在于所含字母数为偶数的回文的中心可以处于两字母之间（例如“abba” 的中心在两个‘b’ 之间）。
按照官方的写法，我们需要以某个字符为中心，假定它是奇数回文串的中心，扩展一次，然后假定它是偶数回文串的中心，扩展一次。比较奇数串和偶数串两个回文串长度，最后确认回文串最大长度。这里我们提前借用一下马拉车算法的想法，改进一下官方给的中心扩展法。我们对输入的字符串，每两个中间插入一个特殊字符，譬如"#"，将形如"abcba"的奇数串变成"#a#b#c#b#a#"，将偶数串"abba"变成"#a#b#b#a#"，这样他们就都是奇数串了，我们只按照奇数串的中心进行扩展来算即可，得到最大子串后，长度除以2，将子串替换掉特殊字符就得到最大子串了。

/**

 * @param {string} s

 * @return {string}

 */

var longestPalindrome = function (s) {

    if (s.length === 0) return '';

    let sp = '#';

    let str = sp + s.split('').join(sp) + sp;

    let maxRadius = -1;

    let maxCenter = -1;

    for (let i = 0, lens = str.length; i < lens; i++) {

        let radius = expandAroundCenter(str, i);

        if (radius > maxRadius) {

            maxRadius = radius;

            maxCenter = i;

        }

    }

    return s.slice(maxCenter / 2 - maxRadius / 2 + 1, maxCenter / 2 + maxRadius / 2);

};

function expandAroundCenter(s, center) {

    let radius = 1;

    let lens = s.length;

    let left, right;

    do {

        left = center - radius;

        right = center + radius;

        if (left < 0 || right > lens - 1) break;

        if (s[left] === s[right]) {

            radius++;

        } else {

            break;

        }

    } while (true);

    return radius;

}

由于我们将长度为n的字符串扩展成长度为2n+1的字符串了，所以最差的情况下，我们比较的次数并不比官网的写法比较2轮(一次将该字符当成奇数回文串中心，一次当成偶数回文串中心)n个字符共计2n次快多少，我们能不能进一步优化，使时间减少一半，变成n呢？
改进：很容易想到，如果有最大的回文字符串，从最中心开始往外扩展，肯定能先找到最大的串，因此可以从扩展后的字符串中心字符开始往两端查找最大回文串，当找到第i个时，如果剩下的字符串不够最大半径时，也就是不可能比当前已经得到的最大字符串大了，就直接退出。代码如下：

/**

 * @param {string} s

 * @return {string}

 */

var longestPalindrome = function (s) {

    if (s.length === 0) return '';

    let sp = '#';

    let str = sp + s.split('').join(sp) + sp;

    let maxRadius = -1;

    let maxCenter = -1;

    let lens = str.length;

    let middle = Math.floor(lens / 2);

    for (let i = middle; i < lens; i++) {

        if (lens - i < maxRadius) break;

        let radius = expandAroundCenter(str, i);

        if (radius > maxRadius) {

            maxRadius = radius;

            maxCenter = i;

        }

    }

    for (let i = middle; i > -1; i--) {

        if (i < maxRadius - 1) break;

        let radius = expandAroundCenter(str, i);

        if (radius > maxRadius) {

            maxRadius = radius;

            maxCenter = i;

        }

    }

    return s.slice(maxCenter / 2 - maxRadius / 2 + 1, maxCenter / 2 + maxRadius / 2);

};

function expandAroundCenter(s, center) {

    let radius = 1;

    let lens = s.length;

    let left, right;

    do {

        left = center - radius;

        right = center + radius;

        if (left < 0 || right > lens - 1) break;

        if (s[left] === s[right]) {

            radius++;

        } else {

            break;

        }

    } while (true);

    return radius;

}

可以看到时间已经减少为普通方式的一半了。

Manacher(马拉车)算法：马拉车算法 Manacher's Algorithm 是用来查找一个字符串的最长回文子串的线性方法，由一个叫Manacher的人在1975年发明的，这个方法的最大贡献是在于将时间复杂度提升到了线性O(n)。
核心思想如下：
先通过插入字符法将长度为n的字符串变成长度2n+1的字符串；
用一个数组Radius[2n+1]记录下以每个字符i为中心的最长半径；
对于已经计算过的最长子串，记录下它的对称中心Center，以及它的最右边界RBorder = Center + Radius[Center];
对于当前判断到的字符i，以它为中心的最大子串可能会有以下情况：
假如这个字符在最右边界里，也就是i<=RBorder，那么它关于对称中心Center一定存在一个对称点i_symmetric，使得Raidus[i] = Radius[i_sysmmetric]，又因为Center - i_symmetric = i - Center，也就是i_symmetric = 2*Center - i;
考虑此时以i为中心点的最大子串，其最右边界可能会大于我们现有的RBorder，如下图的i2;也有可能比现有的RBorder小，如下图的i1；对i1来说比较简单，它的Radius[i] = Radius[i_sysmmetric]即可；但对于i2来说，它就需要重新计算，但它至少可以从RBorder - i为半径开始重新计算。

c	b	a	b
↑	↑	↑	↑
Center	\|	\|	RBorder
	i1	i2

假如这个字符的最右边界超过最大子串的最右边界了，也就是i + radius[i]>RBorder了，就重新更新边界和Center，因为不超过原RBorder里的字符都处理完了。

/**

 * @param {string} s

 * @return {string}

 */

var longestPalindrome = function (s) {

    //扩展字符串

    if (s.length === 0) return '';

    let sp = '#';

    let str = sp + s.split('').join(sp) + sp;

    let center = -1;

    let radius = [];

    let rBorder = -1;

    //这俩变量只是为了输出第一个最大子串，因为越往后走，center和rborder就往后走了

    let maxCenter = -1, maxRadius = -1;

    for (let i = 0, lens = str.length; i < lens; i++) {

        radius[i] = rBorder > i ? Math.min(radius[2 * center - i], rBorder - i) : 1;

        while (str[i + radius[i]] && str[i - radius[i]] && str[i + radius[i]] === str[i - radius[i]]) {

            radius[i]++;

        }

        if (i + radius[i] > rBorder) {

            center = i;

            rBorder = i + radius[i];

        }

        //仅仅只是为了记录第一个最长子串，不是核心算法

        if (radius[i] > maxRadius) {

            maxCenter = i;

            maxRadius = radius[i];

        }

    }

    return s.slice(maxCenter / 2 - maxRadius / 2 + 1, maxCenter / 2 + maxRadius / 2);

}

巴特西

LeetCode Day 5

思路

最新文章

热门文章