Got TLE by DP approach


  • 0
    L

    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];
    }};

  • 1
    C

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


  • 0
    L

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


Log in to reply
 

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