Always Time Limit Exceeded??


  • 3
    S

    Following the hint from "chenyuan53618" (thanks so much!), I modified the code as the blow. The idea is to first use DP to check the palindrome conditions for all substring s(i to j) and then to use DP to solve the min cut. Finally this is accepted.

    class Solution {
    public:
        int minCut(string s) {
            int n = s.size();
            vector<bool> f(n+1, false); f[0] = true;
            vector<int> ncut(n+1, n); ncut[0] = 0;
            vector<vector<bool> > table;
            palindrometable(s, table);
            
            for(int i=1; i<=n; i++) {
                for(int j=0; j<i; j++) {
                    if(f[j] && table[j][i-1]) {
                        f[i] = true;
                        if(j==0) {
                            ncut[i] = 0; 
                            break;
                        }
                        else
                            ncut[i] = min(ncut[i], ncut[j]+1);
                    } // if f[j]
                } //for j=0
            }//for i=1
            
            return ncut[n];
        }
        
        void palindrometable(string s, vector<vector<bool>> &table) {
    	    int n = s.size();
    	    table.resize(n);
    	    for(int i=0; i<n; i++) { 
    		    table[i].resize(n);
    		    for (int j=0; j<n; j++) table[i][j] = false;
    	    }
    	
    	    for(int len=1; len<=n; len++) {
        	    for(int i=0; i<=n-len; i++) {
        		    int j = i+len-1;
        		    if(i==j) table[i][j] = true;
        		    else if(j==i+1 && s[i]==s[j]) table[i][j] = true;
        		    else if(table[i+1][j-1] && s[i]==s[j]) table[i][j] = true;
        	    }
            }
            return;
        }
    };
    

    I always gets "Time Limit Exceeded" for a crazy long "aaaa.....aaaa" test string? Any clue how to avoid it?

    class Solution {
    public:
        int minCut(string s) {
            // IMPORTANT: Please reset any member data you declared, as
            // the same Solution instance will be reused for each test case.
            if(ispalindrome(s)) return 0;
            int n = s.size();
            vector<bool> f(n+1, false); f[0] = true;
            vector<int> ncut(n+1, INT_MAX); ncut[0] = 0;
            
            for(int i=1; i<=n; i++) {
                for(int j=0; j<i; j++) {
                    string w = s.substr(j, i-j);
                    if(f[j] && ispalindrome(w)) {
                        f[i] = true;
                        if(j==0) {
                            ncut[i] = 0; 
                            break;
                        }
                        else
                            ncut[i] = min(ncut[i], ncut[j]+1);
                    } // if f[j]
                } //for j=0
            }//for i=1
            
            return ncut[n];
        }
        
        bool ispalindrome(string s){
            int n = s.size();
            for(int i=0; i<n/2; i++)
                if(s[i]!=s[n-1-i]) return false;
            return true;
        }

  • 0

    Could you please explain your algorithm a bit? Question which shows that you have done your research before asking one will be more likely answered. Thanks!


  • 6
    C

    The reason why it always exceed time limitation is that it need O(nnn), which is not good enough.
    And I figure out the function ispalindrome is where you can work on. It check the whole substring again and again. If you could judge a string use the stored information, probably you can reduce the time complexity. For example, if I knew String(i,j) is a palindrome, then we just need to check if character i-1 and character j+1 are equal instead of the whole String(i-1,j+1) again.


  • 0
    Z

    when using a brute force algorithm, why Palindrome Partitioning will not TLE, while Palindrome Partitioning II will TLE?


  • 0
    S

    Because Palindrome Partitioning need all possible partition, the scale of output will be huge. But all II needs is a number, if you try to generate all possible partition then find which is the minimum cut, it must be a waste of time complexity.


  • 0
    Z

    So, if we use the bruteforce algorithm on both problems, their time complexity are the same, right?


  • 0
    S

    Yes, I think so.


  • 0
    F

    For your consideration, this is my code. I simplify your second part.

    class Solution {
    public:
        int minCut(string s) {
            vector<vector<bool>> mark(s.length(), vector<bool>(s.length(), false));
            for(int len = 1; len <= s.length(); ++len){
                for(int start = 0; start < s.length(); ++start){
                    int end = start + len - 1;
                    end = end > s.length() - 1 ? s.length() - 1 : end;
                    if(start == end){
                        mark[start][end] = true;
                    }else if(start + 1 == end){
                        mark[start][end] = s[start] == s[end];
                    }else{
                        mark[start][end] = s[start] == s[end] && mark[start+1][end-1];
                    }
                }
            }
            vector<int> minCuts(s.length(), s.length() - 1);
            minCuts[0] = 0;
            for(int k = 1; k < s.length(); ++k){
                if(mark[0][k])
                    minCuts[k] = 0;
                for(int p = 0; p < k; ++p){
                    if(mark[p+1][k]){
                        minCuts[k] = min(minCuts[k], minCuts[p] + 1);
                    }
                }
            }
            return minCuts.back();
        }
    
    };

  • 0
    S

    Hi @feng4. Thanks for your post. However it would be better to post an answer with more detail content, not only code. Please read the FAQ (http://oj.leetcode.com/discuss/faq) for more info.


Log in to reply
 

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