LeetCode5. Longest Palindromic Substring（动态规划）

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日 星期一