凌云的博客

成功=工作+游戏+少说空话

LeetCode 算法题 5. Longest Palindromic Substring

分类:algorithm| 发布时间:2016-06-27 00:28:00


题目

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题意

找出最长的回文子串

解法1

遍历给出的字符串,假设 i 为正在遍历的字符的下标, 查出以 i 为中心的回文长度,需要注意长度为奇数和偶数的情况。 记录下最长的回文长度和起始下标。

class Solution {
public:
    string longestPalindrome(string s) {
        int longestBeg = 0, longestLen = 0;
        int curBeg = 0, curLen = 0;
        const int size = s.size();
        for (int i = 0; i != size; ++i) {
            if (longestLen > 2 * (size - i) + 1) {
                break;
            }

            getPalindrome(s, size, i, curBeg, curLen);
            if (curLen > longestLen) {
                longestBeg = curBeg;
                longestLen = curLen;
            }
        }

        return string(s, longestBeg, longestLen);
    }

private:
    void getPalindrome(const string &s, int size, int off, int &beg, int &len) {
        if (!off) {
            beg = 0;
            len = 1;
            return;
        }

        int oddbeg, oddlen;
        int evenbeg, evenlen;
        oddPalindrome(s, size, off, oddbeg, oddlen);
        evenPalindrome(s, size, off, evenbeg, evenlen);
        if (oddlen > evenlen) {
            beg = oddbeg;
            len = oddlen;
        } else {
            beg = evenbeg;
            len = evenlen;
        }
    }

    void oddPalindrome(const string &s, int size, int off, int &beg, int &len) {
        beg = off - 1;
        int end = off + 1;
        while (s[beg] == s[end]) {
            if (beg == 0 || end == size - 1) {
                break;
            }

            --beg;
            ++end;
        }

        if (s[beg] != s[end]) {
            ++beg;
            --end;
        }

        len = end - beg + 1;
    }

    void evenPalindrome(const string &s, int size, int off, int &beg, int &len) {
        beg = off - 1;
        int end = off;
        while (s[beg] == s[end]) {
            if (beg == 0 || end == size - 1) {
                break;
            }

            --beg;
            ++end;
        }

        if (s[beg] != s[end]) {
            ++beg;
            --end;
        }

        len = end - beg + 1;
    }
};

解法2(Manacher's algorithm)

算法原理:

Wikipeida: Longest palindromic substring Manacher's ALGORITHM: O(n)时间求字符串的最长回文子串

如上的算法,算回文长度时需要考虑长度为奇数以及偶数的情况。 在 Manacher's algorithm 中,通过在原字符串插入未出现过的字符串的方式, 巧妙地将所有回文都变成奇数长度。

比如,插入的字符为 #

s     1     2     2     1     2     3     2     1
S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #

然后用一个数组 P[i] 来记录以字符S[i]为中心的最长回文子串向左/右扩张的长度 (包括S[i],也就是把该回文串“对折”以后的长度),比如S和P的对应关系:

S  #  1  #  2  #  2  #  1  #  2  #  3  #  2  #  1  #
P  1  2  1  2  5  2  1  4  1  2  1  6  1  2  1  2  1
(p.s. 可以看出,P[i]-1正好是原字符串中回文串的总长度)

那么怎么计算P[i]呢? 该算法增加两个辅助变量 id和mx,其中 id 为已知的 {右边界最大} 的回文子串的中心, mx 则为 id+P[id],也就是这个子串的右边界。

然后可以得到一个这么一个结论:如果mx > i,那么P[i] >= MIN(P[2 * id - i], mx - i)。 也可以写成:

//记j = 2 * id - i,也就是说 j 是 i 关于 id 的对称点(j = id + (id - i))
if (mx - i > P[j])
    P[i] = P[j];
else /* P[j] >= mx - i */
    P[i] = mx - i; // P[i] >= mx - i,取最小值,之后再匹配更新。

当然光看代码还是不够清晰,还是借助图来理解比较容易。

当 mx - i > P[j] 的时候,以S[j]为中心的回文子串包含在以S[id]为中心的回文子串中, 由于 i 和 j 对称,以S[i]为中心的回文子串必然包含在以S[id]为中心的回文子串中, 所以必有 P[i] = P[j],见下图。

当 P[j] >= mx - i 的时候,以 S[j] 为中心的回文子串不一定完全包含于以 S[id] 为中心的回文子串中, 但是基于对称性可知,下图中两个绿框所包围的部分是相同的, 也就是说以 S[i] 为中心的回文子串,其向右至少会扩张到 mx 的位置, 也就是说 P[i] >= mx - i。 至于 mx 之后的部分是否对称,就只能老老实实去匹配了。

对于 mx <= i 的情况,无法对 P[i]做更多的假设,只能P[i] = 1,然后再去匹配了。

//输入,并处理得到字符串s
int p[1000], mx = 0, id = 0;
memset(p, 0, sizeof(p));
for (i = 1; s[i] != '\0'; i++) {
    p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
    while (s[i + p[i]] == s[i - p[i]]) p[i]++;
    if (i + p[i] > mx) {
        mx = i + p[i];
        id = i;
    }
}

对于原题,解法如下:

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        string S(s.size() * 2 + 2, '#');
        S[0] = '$';
        const int size = S.size();
        for (int i = 2; i < size; i += 2) {
            S[i] = s[(i - 1) / 2];
        }

        int p[size];
        fill(p, p + size, 0);
        int longest = 0, longestIdx = 0;
        int id = 0, mx = 0;
        for (int i = 0; i != size; ++i) {
            int j = 2 * id - i;
            p[i] = mx > i ? min(p[j], mx - i) : 1;
            while (S[i - p[i]] == S[i + p[i]]) {
                ++p[i];
            }

            if (longest < p[i]) {
                longest = p[i];
                longestIdx = i;
            }

            if (i + p[i] > mx) {
                id = i;
                mx = i + p[i];
                if (mx >= size) {
                    break;
                }
            }
        }

        int longestBeg = longestIdx - longest + 1;
        int longestLen = 2 * (longest - 1)+ 1;
        string retTmp(S, longestBeg, longestLen), ret;
        int retSize = retTmp.size();
        for (int i = 1; i < retSize; i +=2 ) {
            ret.push_back(retTmp[i]);
        }

        return ret;
    }
};