MENU

LeetCode5. Longest Palindromic Substring(动态规划)

2019 年 04 月 15 日 • 阅读: 1715 • LeetCode阅读设置

LeetCode5. Longest Palindromic Substring(动态规划)

  • Medium
  • Accepted:522,460
  • Submissions:1,936,088

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"

链接

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

题意

给定一个字符串s,求s的最长公共子串。

题解

这题很经典了,解法有很多种。

  • 一种最暴力的办法是两层循环求子串,一层循环判断是否为回文串,时间复杂度$O(n^3)​$
  • 把问题转化一下,求s的最长公共子串等价于求s和s的反转s'的最长公共子串,时间复杂度$O(n^2)​$
  • 直接使用动态规划,假设dp[i][j]表示$s_{i, j}​$间的最长回文子串长度,那么我们要求的是dp[0][n-1],显然,如果s[i] == s[j]:

    • j == i + 1时,dp[i][j] = 2;
    • j > i + 1时, dp[i][j] = (dp[i + 1][j - 1] == 0) ? 0 : dp[i + 1][j - 1] + 2;,注意这里当dp[i + 1][j - 1]为0时即使s[i] == s[j],dp[i][j] 依然为0
    • 第一层循环i从n-2到0,第二层循环j从i+1到n-1,加两个变量记录位置和长度
    • 时间复杂度$O(n^2)​$
  • 动态规划的另一种方法,使用dp[i][j]表示$s_{i, j}​$是否为回文子串,当s[i] == s[j]时:

    • dp[i][j] = (j - i <= 2) || dp[i+1][j-1]
    • 时间复杂度$O(n^2)$
  • 还有一种专门的做法是使用马拉车算法,时间复杂度$O(n)$,之前有写过,HDU3036 最长回文(最长回文子串)

代码

  • Runtime: 232 ms, faster than 21.36% of C++ online submissions for Longest Palindromic Substring.
  • Memory Usage: 186.8 MB, less than 12.99% of C++ online submissions for Longest Palindromic Substring.
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n == 0 || n == 1)
            return s;
        string res = "";
        vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));
        for (int i = 0; i < n; ++i)
            dp[i][i] = 1;
        int pos = 0, maxLen = 1;
        for (int i = n - 2; i >= 0; --i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (s[i] == s[j])
                {
                    if (j == i + 1)
                        dp[i][j] = 2;
                    if (j > i + 1)
                        dp[i][j] = (dp[i + 1][j - 1] == 0) ? 0 : dp[i + 1][j - 1] + 2;
                    if (dp[i][j] > maxLen)
                    {
                        maxLen = dp[i][j];
                        pos = i;
                    }
                }
                else
                    dp[i][j] = 0;
            }
        }
        for (int i = pos; i < pos + maxLen; ++i)
            res += s[i];
        return res;
    }
};
  • Runtime: 168 ms, faster than 31.27% of C++ online submissions for Longest Palindromic Substring.
  • Memory Usage: 18.8 MB, less than 39.81% of C++ online submissions for Longest Palindromic Substring.
class Solution {
public:
    string longestPalindrome(string s) {
        int n = s.length();
        if (n < 2)
            return s;
        string res = "";
        vector<vector<bool >> dp(n + 1, vector<bool >(n + 1, 0));
        for (int i = 0; i < n; ++i)
            dp[i][i] = true;
        int pos = 0, maxLen = 1;
        for (int i =  n - 2; i >= 0; --i)
        {
            for (int j = i + 1; j < n; ++j)
            {
                if (s[i] == s[j] && (j - i <= 2 || dp[i + 1][j - 1]))
                {
                    dp[i][j] = true;
                    if (j - i + 1 > maxLen)
                    {
                        maxLen = j - i + 1;
                        pos = i;
                    }
                }
            }
        }
        for (int i = pos; i < pos + maxLen; ++i)
            res += s[i];
        return res;
    }
};

The end.
2019年4月15日 星期一