A O(n^2) solution. whyt got "Time Limit Exceeded" in C++


  • 0
    N

    l use dp method to slove the problem, an array is used to store the status if i to j is Palindromic Substring ,
    in the for loop lt take o(n^2) times ,but why still get "time limit exceeded" on test case "aaaaaa....aaa"
    could the admin not close my post?

    {

    //dp from top to down
    string longestPalindrome(string s) {
        int nsize=s.length();
        if(nsize<=1){
            return s;
        }
        bool vec[1001][1001];
        for(int i=0;i<nsize;i++){
            for(int j=0;j<nsize;j++){
                if(i==j)
                    vec[i][j]=true;
                else
                    vec[i][j]=false;
            }
        }
        int max=0;
        int maxidx=-1;
        for(int i=nsize-1;i>=0;i--){
            for(int j=nsize-1;j>i;j--){
                if((j-i)==1){
                    vec[i][j] = s[i]==s[j];
                }else{
                    vec[i][j] = ((s[i]==s[j])&&vec[i+1][j-1]);
                }
                if(vec[i][j]==true&&(j-i+1)>max){
                    max=j-i+1;
                    maxidx=i;
                }
            }
        
        }
        if(maxidx!=-1&&max>0)
            return s.substr(maxidx,max);
        else
            return "";
    }
    

    }


  • 0
    C

    Just change the first O(n^2) loop to O(n)

    for(int i=0;i<nsize;i++){
        vec[i][i]=true;
    }

  • 0
    Y

    use memset to set vec to all 0


Log in to reply
 

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