# Got TLE by DP approach

• Could anybody help me improve this code. I still do not know why I get TLE. I suspect the copy function in the loop, but I do not know how other ways to hold dp values.

IDEA:
At step #i, dp[j] (j<=i) holds the longest palindrome string between j and i. We only need dp at previous step, so I use tmp to hold it.

PS: I got MLE if I create dp[n][n], that's why I choose to use tmp to hold previous value of dp.

Confirmation: Is The complexity O(n^2)??

Thanks a lot.

``````class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
string dp[1001]; // bottom up
string tmp[1001]; // store a copy of dp
if(n<=1){
return s;
}

For(i,0,n){dp[i]=tmp[i]="";}
dp[0]+=s[0];
for(int i =1; i<n; i++){
copy(dp,dp+i+1,tmp);
dp[i] = string(1,s[i]);
for(int j = i-1; j>=0; j--){
if(s[i]==s[j]){
dp[j] = string(1,s[i]) + tmp[j+1]+string(1,s[i]);
}
else{
if(tmp[j].size() > dp[j+1].size())
dp[j] = tmp[j];
else
dp[j] = dp[j+1];
}
}
}
return dp[0];
}};``````

• You are storing too many temporary strings. Use bool dp[1000][1000] instead

• Thank you, I got the correct answer. I unnecessarily complicated the problem.

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