C++ 8ms solution (terminate the code in advance to save plenty of time)


  • 0
    class Solution {
    
    public:
    bool checkPalindrome(string & s, int i, int j){
        while(i<j){
            if (s[i]!=s[j]) return false;
            i++;j--;
        }
        return true;
    }
    int minCount(string s,int k, vector<int> &hist) {
        if (k>=s.size()) return 0;
        if (k==s.size()-1) return 1;
        if (checkPalindrome(s,k,s.size()-1)) return 1;  // key 1, terminate in advance
        int minC = INT_MAX;
        for (int i=s.size()-1;i>=k;i--){   // important, check from long substr to short ones, saving lots of time
            if (checkPalindrome(s,k,i)) {
                int temp = 1;
                if (hist[i+1]==INT_MAX) {
                    hist[i+1]=minCount(s,i+1,hist);
                }
                temp+=hist[i+1];
                minC = minC<temp?minC:temp;
                if (minC==2) return minC;   // key 2, terminate in advance
            }
        }
        return minC;
    }
    int minCut(string s) {
        if (s.size()<=1) return 0;
        vector<int> hist(s.size()+1,INT_MAX);
        return minCount(s,0,hist)-1;
    }
    };

  • 0
    P

    I feel because it is not in the worst case.
    If you change the loop in minCount() to be for(int i=k;i<s.size();i++) or remove the terminate statement:{if (minC==2) return minC;} It will exceed time limit.


  • 0
    B

    here is a more concise version

    class Solution {
    public:
        int minCut(string s) 
        {
            if(s.length()<2) return 0;
            vector<int>cut(s.length(),INT_MAX);
            return help(s,cut,0,s.length()-1);
        }
        
        int help(string & s, vector<int> & cut, int left, int right)
        {
            if(left>right || isPal(s,left,right)) return 0;
            int minCut = INT_MAX;
            for(int i = right; i>= left; i--)
            {
                if(isPal(s,left,i))
                {
                    if(cut[i]==INT_MAX) cut[i] = help(s,cut,i+1,right);
                    if(cut[i]==0) return 1;
                    minCut = min(minCut, 1+cut[i]);
                }
            }
            return minCut;
        }
        
        bool isPal(string & s, int left, int right)
        {
            while(left<right) 
                if(s[left++]!=s[right--]) return false;
            return true;
        }
    };

Log in to reply
 

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