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

• ``````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;
}
};``````

• 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.

• 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;
}
};``````

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