# Two C++ O(N^2) methods

• ``````class Solution {
public:
/**method 1 中心扩展法**//*
int cen1,cen2,len,r;
void check(int pos,const string &s){
int i=1;
while(pos-i>=0 && pos+i<s.size() && s[pos-i]==s[pos+i]){
i++;
}
if(2*(i-1)+1>len){
len = 2*(i-1)+1;
r = i-1;
cen1 = pos;
cen2 = -1;
}

}
void check(int pos1,int pos2,const string &s){
int i = 1;
while(pos1-i>=0 && pos2+i<s.size() && s[pos1-i]==s[pos2+i]){
i++;
}
if(2*i>len){
len = 2*i;
r = i-1;
cen1 = pos1;
cen2 = pos2;
}
}
string longestPalindrome(string s) {
if(s.empty()) return s;
cen1 = 0;cen2 = -1;
len = 1; r = 0;
for(int i=0;i<s.size()-1;++i){
check(i,s);
if(s[i]==s[i+1])
check(i,i+1,s);
}
if(cen2==-1){
return s.substr(cen1-r,len);
}else{
return s.substr(cen1-r,len);
}
}
*/
/**method 2 dp**/
string longestPalindrome(string s) {
vector<vector<bool>> dp(s.size(),vector<bool>(s.size(),false));
int pos = 0,len = 1;
for(int i=0;i<s.size();++i) {
dp[i][i] = true;
if(i+1<s.size() && s[i]==s[i+1]) {
dp[i][i+1] = true;
pos = i;
len = 2;
}
}
for(int l = 3;l<=s.size();++l){
for(int i=0;i<s.size()-l+1;++i){
int j = i+l-1;
if(s[i]==s[j] && dp[i+1][j-1]){
dp[i][j] = true;
pos = i;
len = l;
}
}
}
return s.substr(pos,len);
}
};
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.