[ LeetCode  ]

LeetCode 5: 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.

解法一:动态规划

使用动态规划只要注意到这个递推关系:用 dp[i][j]==true 表示 s[i:j] 是回文串(两边都闭合)。那么只要子问题 s[i+1:j-1] 是回文串,并且 s[i]==s[j],则 s[i:j] 就是回文串。由此可以编写 DP 算法,下面是 C++ 实现:

class Solution
{

  public:
    string longestPalindrome(string s)
    {
        if (s.empty())
            return "";
        if (s.size() == 1)
            return s;

        int n = s.length();
        string res("");

        bool dp[n][n];
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                dp[i][j] = false;
            }
        }

        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                dp[i][j] = s[i] == s[j] && (j - i < 3 || dp[i + 1][j - 1]);

                if (dp[i][j] && res.length() < j - i + 1)
                {
                    res = s.substr(i, j - i + 1);
                }
            }
        }

        return res;
    }
};

这个实现的时间复杂度是 $O(N^2M)$,$M$ 是最大回文串的长度。因为 std::string.substr 的计算复杂度和返回字符串的长度呈线性关系。

空间复杂度为 $O(N^2)$。所以用 DP 来解虽然容易理解,但效率不高。

后记

这是我用 C++ 做的第一道题,才发现我对 C++ 实际上一点儿也不熟悉。这次学到两个知识点: