该题是找最长回文串,只需要O(n^2)的复杂度求解就能通过,其思路也好像,但是问题在于我用的string 类型的+操作使得时间浪费太多,总是超时,代码如下:
class Solution {
public:
string longestPalindrome(string s) {
string res="";
if(s.size()<=1)return s;
int n=s.size();
for(int i=0;i<n;i++){
string s1="",s2="";
int count1=0,count2=0;
s1+=s[i];
for(int j=1;j<=i&&j<s.size()-i;j++){
if(s[i-j]==s[i+j])
s1=s[i-j]+s1+s[i+j];
else{break;}
}
for(int j=0;j<=i&&j<s.size()-i-1;j++){
if(s[i-j]==s[i+j+1])s2=s[i-j]+s2+s[i+j+1];
else {break;}
}
if(s1.size()>res.size())res=s1;
if(s2.size()>res.size())res=s2;
}
return res;
}
};
后来发现这个问题之后,将字符拼接的操作改成字符拷贝,就可以通过了,代码如下:
class Solution {
public:
string longestPalindrome(string s) {
string res="";
if(s.size()<=1)return s;
int n = s.size();
for(int i=0;i<n;i++){
string s1="",s2="";
int l = i, r = i;
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l--;
r++;
}
s1=s.substr(l+1, r-l-1);
if(s1.size()>res.size())res=s1;
l = i; r = i+1;
while (l >= 0 && r <= n-1 && s[l] == s[r]) {
l--;
r++;
}
s2=s.substr(l+1, r-l-1);
if(s2.size()>res.size())res=s2;
}
return res;
}
};
最好说一句,其实本题还有O(N)时间解决的方法,原文件见http://blog.csdn.net/feliciafay/article/details/16984031 有详细说明及代码,我就不赘述了。