5. Longest Palindromic Substring
难度:Medium
刷题内容
原题连接
- 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"
解题方案
思路 1 **- 时间复杂度: O(N^2)*- 空间复杂度: O(N^2)***
这题如果用单纯暴力的解法，时间复杂度为 O(n ^ 3)，肯定超时，那么就要对这个算法进行优化，这里采用的是DP思想，定义 p(i,j)为s中的第i个数到s中的第j个数的子串，不难看出 p(i，j)中的子串有重复计算，接下来就可以写出状态转移方程 P(i,j)=(P(i+1,j?1) and S[i] == S[j])
class Solution {
public:
int dp[1000][1000] = {0};
string longestPalindrome(string s) {
int beg = 0,en = 1,ans = 0;
int length = s.length();
for(int i = 0;i < length;++i)
{
dp[i][i] = 1;
if(i + 1 < length && s[i] == s[i + 1])
dp[i][i + 1] = 1;
}
for(int i = 0;i < length;++i)
for(int j = 0;j <= i;++j)
{
if(i > j + 1)
dp[j][i] = (dp[j + 1][i - 1] && s[i] == s[j]);
if(dp[j][i] && i - j + 1 > ans)
{
ans = i - j + 1;
beg = j;
en = i + 1;
}
}
string ret(s.begin() + beg,s.begin() + en);
return ret;
}
};
