5. Longest Palindromic Substring (Medium)

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

Solution 1: Brute Force

Time Complexity: $$O(n^2)$$

以每一个字符为中心，像两边扩散来寻找回文串，这个算法的时间复杂度是O(n*n)，可以通过OJ，就是要注意奇偶情况，由于回文串的长度可奇可偶，比如"bob"是奇数形式的回文，"noon"就是偶数形式的回文，两种形式的回文都要搜索，参见代码如下：

class Solution {
    void check(string s, int l, int r, int& start, int& len) {
        while (l-1 >= 0 && r+1 < s.size() && s[l-1] == s[r+1]) {
            --l; ++r;
        }
        // updata value
        int curlen = r-l+1;
        if (len < curlen) {
            len = curlen;
            start = l;
        }
    }

public:
    string longestPalindrome(string s) {
        int start = 0, len = 0;
        for (int i = 0; i < s.size(); ++i) {
            // noon
            if (i+1 < s.size() && s[i] == s[i+1]) {
                check(s, i, i+1, start, len);
            }
            // bob
            check(s, i, i, start, len);
        }
        return s.substr(start,len);

    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() < 2) return s;
        int l = 0, r = 0, n = s.size(), maxlen = 0, maxstart = 0;
        for (int i = 0; i < n && n-i > maxlen/2;) {
            l = r = i;
            while (r < n-1 && s[r] == s[r+1]) ++r; // skip duplicates
            i = r+1;
            while (r < n-1 && l > 0 && s[l-1] == s[r+1]) {
                ++r; --l;
            }
            int len = r-l+1;
            if (len > maxlen) {
                maxlen = len;
                maxstart = l;
            }
        }
        return s.substr(maxstart, maxlen);
    }
};

Solution 2: DP

Time Complexity: $$O(n^2)$$

维护一个二维数组dp，其中dp[i][j]表示字符串区间[i, j]是否为回文串，当i = j时，只有一个字符，肯定是回文串，如果j = i + 1，说明是相邻字符，此时需要判断s[i]是否等于s[j]，如果i和j不相邻，即j - i >= 2时，除了判断s[i]和s[j]相等之外，dp[i + 1][j - 1]若为真，就是回文串，通过以上分析，可以写出递推式如下：

dp[i, j] = 1                                     if i == j

           = s[i] == s[j]                        if j = i + 1

           = s[i] == s[j] && dp[i + 1][j - 1]    if j > i + 1

这里有个有趣的现象就是如果我把下面的代码中的二维数组由int改为vector >后，就会超时，这说明int型的二维数组访问执行速度完爆std的vector啊，所以以后尽可能的还是用最原始的数据类型吧。

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.size() == 0) return "";
        bool dp[s.size()][s.size()] = {false};
        int l = 0, r = 0, len = 1;
        for (int j = 0; j < s.size(); ++j) {
            dp[j][j] = true;
            for (int i = 0; i < j; ++i) {
                if (i+1 == j) dp[i][j] = (s[i] == s[j]);
                else dp[i][j] = (s[i] == s[j] && dp[i+1][j-1]);
                // dp[i][j] = (s[i] == s[j]) && (i+1 == j || dp[i+1,j-1]);

                if (dp[i][j] && j-i+1 > len) {
                    len = j-i+1;
                    l = i; r = j;
                }
            }
        }
        return s.substr(l, len);
    }
};

Solution 3: Manacher's Algorithm

Time Complexity: $$O(n)$$

最后要来的就是大名鼎鼎的马拉车算法Manacher's Algorithm，这个算法的神奇之处在于将时间复杂度提升到了O(n)这种逆天的地步，而算法本身也设计的很巧妙，很值得我们掌握，参见我另一篇专门介绍马拉车算法的博客Manacher's Algorithm 马拉车算法，代码实现如下：

class Solution {
public:
    string longestPalindrome(string s) {
        string t = "$#";
        for (auto c:s) {
            t += c;
            t += "#";
        }
        int p[t.size()] = {0}, id = 0, mx = 0, resId = 0, resMx = 0; 
        for (int i = 0; i < t.size(); ++i) {
            p[i] = mx > i ? min(p[2*id-i], mx-i) : 1;
            while (t[i-p[i]] == t[i+p[i]]) ++p[i];
            if (i+p[i] > mx) {
                mx = i+p[i];
                id = i;
            }
            if (p[i] > resMx) {
                resMx = p[i];
                resId = i;
            }
        }
        return s.substr((resId-resMx)/2, resMx-1);
    }
};

Longest Palindromic Substring Part II 6ms

稍微改了改，每次都查有没有outofbound

class Solution {
    string preProcess(string& s) {
        string t("#");
        for (auto c: s) {
            t += c; t += "#";
        }
        return t;
    }
public:
    string longestPalindrome(string s) {
        string t = preProcess(s);
        // cout << t << endl;
        int n = t.size(), C = 0, R = 0, mC = 0, mlen = 0;
        vector<int> P(n, 0);
        for (int i = 1; i < n-1; ++i) {
            int i_mirror = 2*C-i; // equals to i' = C - (i-C)
            P[i] = (R > i) ? min(P[i_mirror], R-i):0;
            while (i-P[i]-1 >= 0 && i+P[i]+1 < n && t[i-P[i]-1] == t[i+P[i]+1]) ++P[i];
            //cout << t[i] << " " << P[i] << endl;
            if (i+P[i] > R) {
                C = i; R = i+P[i];
            }
            if (mlen < P[i]) {
                mC = i; mlen = P[i];
            }
        }
        return s.substr((mC-mlen)/2, mlen);
    }
};