5.Longest Palindromic Substring¶

5.Longest Palindromic Substring¶

Tags: Medium String Dynamic Programming

Links: https://leetcode.com/problems/longest-palindromic-substring/

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

Example 1:

Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example 2:

Input: "cbbd"
Output: "bb"

class Solution {
public:
    string longestPalindrome(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        preProcess(s);
        int n = s.size();
        vector<int> p(n);
        //mx 是回文串能延伸到的最右端的位置
        //mid为能延伸到最右端的位置的那个回文子串的中心点位置
        int mid = 1, mx = 1, len = 0;
        int pos = 1;
        for (int i = 1; i < n; ++i) {
            if (i < mx) p[i] = min(mx - i, p[2 * mid - i]);
            else p[i] = 1;
            while (s[i + p[i]] == s[i - p[i]]) ++p[i];
            if (i + p[i] > mx) {
                mid = i;
                mx = i + p[i];
            }
            if (p[i] - 1 > len) {
                len = p[i] - 1;
                pos = i;
            }
        }

        string tmp = s.substr(pos - p[pos] + 1, 2 * p[pos] - 1);
        string res;
        for (auto e : tmp) {
            if (e == '#') continue;
            else res.push_back(e);
        }

        return res;
    }

    void preProcess(string & s)
    {
        string tmp = "$#";
        for (int i = 0; i < s.size(); ++i) {
            tmp.push_back(s[i]);
            tmp.push_back('#');
        }
        tmp.push_back('@');
        s = tmp;
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 10.2 MB, less than 48.27% of C++ online submissions for Longest Palindromic Substring.

manacher算法的变形，需要输出最长的回文串，其实只是多了一个变量来记录最长回文串的对称中心的位置。时间复杂度自然就是 $O(n)$ 了。

这道题目的标签还有动态规划，所以用另一种方法求解：

class Solution {
public:
    string longestPalindrome(string s) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        if (s.size() == 0) return "";
        int n = s.size();
        vector<vector<int>> d(n, vector<int>(n));
        int left = 0, len = 1; //这里需要len = 1才行
        for (int j = 0; j < n; ++j) {
            d[j][j] = 1;
            for (int i = 0; i < j; ++i) {
                d[i][j] = (s[i] == s[j] && (j - i < 2 || d[i + 1][j - 1]));
                if (d[i][j] && j - i + 1 > len) {
                    left = i;
                    len = j - i + 1;
                }
            }
        }

        return s.substr(left, len);
    }
};

Runtime: 212 ms, faster than 20.52% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 186.8 MB, less than 5.51% of C++ online submissions for Longest Palindromic Substring.

动态规划算法的时间复杂度是 $O(n^2)$ ，可以看到差距巨大。

思路是用d[i][j]表示在下标i到j的子串是否是回文串，值为0或1。如果s[i] != s[j]那么此区间一定无法构成回文串，如果s[i] = s[j]，那么依赖于d[i + 1][j - 1]。此时就需要警惕，因为如果j = i + 1，那么会出现i+1> j-1的情况，所以需要在判断的时候注意。

另外一个细节是len代表最长回文串的长度，其初始值必须是1，因为字符串为空的情况已经提前处理了，如果len初始化为0，那么就无法处理s = "a"的情况了，因为在双循环的第二层循环不会进行，返回的结果是个空的字符串。