题目描述

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

样例

示例 1：

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

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

算法1

(动态规划) $O(n^2)$

f[i][j]代表从i到j是否是回文串；
如果是回文串，则更新最长长度，最后输出最长长度即可。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.size();
        vector<vector<bool>> f(n + 1, vector<bool>(n + 1));

        int len = 0, start = -1;
        for (int i = n; i >= 1; --i){
            for (int j = i; j <= n; ++j){
                f[i][j] = s[i - 1] == s[j - 1] && (j - i < 2 || f[i + 1][j - 1]);
                if (f[i][j] && j - i + 1 > len){
                    len = j - i + 1;
                    start = i;
                }
            }
        }
        return s.substr(start - 1, len);
    }
};

可以优化掉一维空间

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.size();
        vector<bool> f(n + 1);

        int len = 0, start = -1;
        for (int i = n; i >= 1; --i){
            f[0] = false;
            bool pre = false;
            for (int j = i; j <= n; ++j){
                bool tmp = f[j];
                f[j] = s[i - 1] == s[j - 1] && (j - i < 2 || pre);
                if (f[j] && j - i + 1 > len){
                    len = j - i + 1;
                    start = i;
                }
                pre = tmp;
            }
        }
        return s.substr(start - 1, len);
    }
};

算法2

(中心线枚举) $O(n^2)$

在每个位置尽可能向外扩张组成回文串，例如”abcba”中的’c’，可以向外扩张成”abcba”, “abba”的两个b之间的缝隙，可以扩张成”abba”；
枚举所有可能，然后取最长的一个即可。

时间复杂度

每个位置枚举两次，最长能扩张到O(n), 所以是$O(n^2)$

参考文献

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int n = s.size();
        int len = 0, start = -1;
        for (int i = 0; i < n; ++i){
            for (int j = i; j <= i + 1; ++j){
                pair<int, int> s_e = grow(s, i, j);
                if (s_e.second - s_e.first > len){
                    len = s_e.second - s_e.first;
                    start = s_e.first;
                }
            }
        }

        return s.substr(start, len);
    }

    pair<int, int> grow(string &s, int start, int end){
        while (start > 0 && end <= s.size() && s[start - 1] == s[end]){
            --start; ++end;
        }
        return {start, end};
    }
};

算法3

(马拉车) $O(n)$

思路类似KMP，运用数组存储过往信息，节省计算量。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        string t = "$#";
        for (char c: s) t += c, t += '#';
        vector<int> p(t.size(), 1);
        int id = 1, mx = 1, max_len = 0, max_idx = 0;
        for (int i = 1; i < t.size(); ++i){
            p[i] = i < mx ? min(p[2 * id - i], mx - id) : 1;
            while (i - p[i] >= 0 && i + p[i] < t.size() && t[i - p[i]] == t[i + p[i]])
                ++p[i];
            if (p[i] > max_len) max_idx = i, max_len = p[i];
            if (i + p[i] > mx) mx = i + p[i], id = i;
        }

        return s.substr((max_idx - max_len) / 2, max_len - 1);
    }
};