# A O(n^2) solution in java passed the oj, but got "Time Limit Exceeded" in C++

• Java Implementation:

public class Solution
{
public String longestPalindrome(String s)
{
if (s==null) return null;

``````    int n = s.length();
if (n<2) return s;

int start = 0;
int end = 0;

boolean[][] M = new boolean[n][n]; // all intialized to false, by default
M[n-1][n-1] = true;
for (int i=0; i<n-1; ++i)
{
M[i][i] = true;
M[i][i+1] = (s.charAt(i)==s.charAt(i+1));

if (M[i][i+1])
{
start = i;
end = i+1;
}
}

for (int step=2; step<n; ++step)
{
for (int i=0; i<=n-1-step; ++i)
{
M[i][i+step] = M[i+1][i+step-1] && s.charAt(i)==s.charAt(i+step);
if (M[i][i+step])
{
start = i;
end = i+step;
}
}
}

return s.substring(start, end+1);
}
``````

}

=======================================

C++ implementation:

``````string longestPalindrome(string s) {
int i, j, n, maxLen = 0;
n = s.length();
if (n <= 1) return s;

vector<vector<bool> > P(n, vector<bool>(n, false));

const char * ptr = s.data();
for (i = 0; i < n; i++){
P[i][i] = true;
}

string retval;
for (i = 0; i < n-1; i++){
P[i][i+1] = (ptr[i] == ptr[i+1]);
if (P[i][i+1]){
retval = s.substr(i, 2);
}
}

for (i = 2; i < n; i++){
for (j = 0; j < n-i; j++){
P[j][j+i] = P[j+1][j+i-1] && (ptr[j] == ptr[j+i]);

if (P[j][j+i] && maxLen < i){
maxLen = i;
retval = s.substr(j, i);
}
}
}

return retval;
}``````

1. Don't call `substr()` everytime you find a better result

2. Don't use `vector` of `vector`, use static array instead.

``````class Solution {
public:
string longestPalindrome(string s) {
int i, j, n, maxLen = 0;
n = s.length();
if (n <= 1) return s;

bool P[1001][1001];
const char * ptr = s.data();
for (i = 0; i < n; i++){
P[i][i] = true;
}

string retval;
int st,le;
for (i = 0; i < n-1; i++){
P[i][i+1] = (ptr[i] == ptr[i+1]);
if (P[i][i+1]){
st = i;
le = 2;
}
}

for (i = 2; i < n; i++){
for (j = 0; j < n-i; j++){
P[j][j+i] = P[j+1][j+i-1] && (ptr[j] == ptr[j+i]);

if (P[j][j+i] && maxLen < i+1){ // Should be i + 1
maxLen = i+1; // Should be i + 1
st = j;
le = i+1; // Should be i + 1
}
}
}
return s.substr(st,le);
}
};``````

• This post is deleted!

• This post is deleted!

• I have got the same confusion,I change the vector to static array and fortunately I get an accept,but I don't know the reason.

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