也是蛮标准的题目了 写了一个dp的O($n^2$)的解法 马拉车的O(n)解法回头有时间来学习吧…
哦空串要单独判断…因为似乎substr对空串即使取0长度也会出问题…
++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
|
#include<string>
#include<cstring>
using namespace std;
class Solution {
public:
string longestPalindrome(string s) {
if(s.empty())
{
return string();
}
int dp[1020][1020],ans=0,start=0;
memset(dp,0,sizeof(dp));
for(int i=0;i<s.length();++i){
dp[i][i]=1;
ans=1;
}
for(int i=0;i<s.length()-1;++i){
if(s[i]==s[i+1]){
dp[i][i+1]=1;
ans=2,start=i;
}
}
for(int i=2;i<s.length();++i){
for(int j=0;j+i<s.length();++j){
if(dp[j+1][j+i-1]&&s[j]==s[j+i]){
dp[j][j+i]=1;
ans=i+1,start=j;
}
}
}
return s.substr(start,ans);
}
};
|