class Solution {
public:
int minCut(string s) {
int n = s.size();
vector<int> cut(n+1, 0); // number of cuts for the first k characters
for (int i = 0; i <= n; i++) cut[i] = i1;
for (int i = 0; i < n; i++) {
for (int j = 0; ij >= 0 && i+j < n && s[ij]==s[i+j] ; j++) // odd length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[ij]);
for (int j = 1; ij+1 >= 0 && i+j < n && s[ij+1] == s[i+j]; j++) // even length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[ij+1]);
}
return cut[n];
}
};
My solution does not need a table for palindrome, is it right ? It uses only O(n) space.


@tqlong
Your logic seems very awesome.Can you please explain your code little bit more? It would be very thankful.

Similar java solution
public int minCut(String s) { if(s.length()==0)return 0; int[]c=new int[s.length()+1]; for(int i=0;i<s.length();i++)c[i]=Integer.MAX_VALUE; c[s.length()]=1; for(int i=s.length()1;i>=0;i){ for(int a=i,b=i;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a,b++) c[a]=Math.min(c[a],1+c[b+1]); for(int a=i,b=i+1;a>=0 && b<s.length() && s.charAt(a)==s.charAt(b);a,b++) c[a]=Math.min(c[a],1+c[b+1]); } return c[0]; }

I'd like to help explain this great algorithm. :O
This divideandconquer algorithm utilize the symmetry of palindromes, so there is no need to cache the result of whether
s[i:j)
is a palindrome.Say that it started at
s[i] = 'b'
, ands[i1,i+1]
is a palindrome "aba":.......aba... <X> ^ <Y>
And we know the least cuts for
s[0,i1)
is X, then the least cuts fors[0,i+1]
Y is not greater than X+1. Last, we need to find out all the palindromes ins[0,i+1]
so as to minimize the number of cuts.
