Why my O(n^2) DP solution always get TLE for long input


  • 0
    A

    Basic idea: Using a vector of vector vvi to record all the possible palindrome position, for example, vvi[i] is not empty only when there is a palindrome starting from s[i] and the element of vvi[i] records all the next possible palindrome starting positions. Vector dp[] is used to store the min cut for sub string s[i,...,n-1]. With the table vvi, one could scan from right of vvi to left to obtain all the element of dp[], output is dp[0];

    Can anyone help me to improve it? Thanks!

        int minCut(string s) {
             int n=s.size();
             if(s.size()==1) return 0;
             if(setTable(s)) return 0;
             vector<int> dp(n);// dp[i] store the minCut for s[i...n-1]
             dp[n-1]=0;
             for(int i=n-2; i>=0;i--){
                    dp[i]=n-i-1;
                    for(auto it=vvi[i].begin();it!=vvi[i].end();it++){
                         if(*it==n) dp[i]=0;
                         if(dp[*it]+1<dp[i]) dp[i]=dp[*it]+1;
                    }
             }
             return dp[0];
        }
        int setTable(string s){ // set up a table vvi such that vvi[i] record all the next Palindrome start position.
             int n=s.size();
             vvi.resize(n);
             for(int i=n-1;i>=0;i--){ // first search how many positions could arrive at the end of s;
                   if(isPalindrome(s.substr(i))) vvi[i].push_back(n);
             }
    
             if(!vvi[0].empty() && vvi[0][0]==n) return 0; //if we there is a palindrome starting 0, then the cut is 0;
             for(int i=s.size()-1;i>=0;i--){
                   if(!vvi[i].empty()){ //if vvi[i] is not empty then start searching all palindromes ended at s[i-1].
                         for(int j=i-1;j>=0;j--){
                            if(isPalindrome(s.substr(j,i-j))) vvi[j].push_back(i); //found one mark vvi[j] with i.
                          }
                   }
             }
             return 1;
        }
        bool isPalindrome(string s){
             if(s.size()==1) return true;
             for(int i=0,j=s.size()-1;i<j;i++,j--){
                       if(s[i]!=s[j]) return false;
              }
              return true;
        }

  • 0
    Y

    your isPalindrome function brings another O(n) in, so in total you algorithm is O(n^3) instead of O(n^2). My first submission is similar to yours.


Log in to reply
 

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