# 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

### 题解

• 一种最暴力的办法是两层循环求子串，一层循环判断是否为回文串，时间复杂度$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日 星期一