# My solution does not need a table for palindrome, is it right ? It uses only O(n) space.

• ``````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] = i-1;
for (int i = 0; i < n; i++) {
for (int j = 0; i-j >= 0 && i+j < n && s[i-j]==s[i+j] ; j++) // odd length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j]);

for (int j = 1; i-j+1 >= 0 && i+j < n && s[i-j+1] == s[i+j]; j++) // even length palindrome
cut[i+j+1] = min(cut[i+j+1],1+cut[i-j+1]);
}
return cut[n];
}
};``````

• Very awesome thought! This seems to be the best solution I've found. It takes O(n^2) time and O(n) space, better than many other solutions! OJ time is less than 56ms, good job! I just wonder why this wonderful solution got so few votes..

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

• Thanks, it works because of the following invariance: cut[k] is correct for every k <= i. You could prove it by induction for i=0,1,2...

• very concise and direct solution！ The best point is that this solution can reduce many unnecessary loops! Because when s[i-j] != s[i+j] , the loop will break. Although the time complexity is also O(n^2), this solution will be quicker!

• Eegant algrothim! I use the almost same idea with you. But I use a dictionary to store the minmum length using much more space. Thanks for your code

• best ever ! thanks so mcuh

• can someone explain the algorithm a little bit? How each cut[] is calculated using the formula?

• If I get it right, each cut at i+j is calculated by scanning (i-j)'s minimum cut + 1 if s[i-j, i+j] is a palindrome. This code is awesome. I was thinking of Manacher's algorithm + DP but your code is wayyyy better.

• This post is deleted!

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

• Most beautiful logic I have came across so far. Thanks for sharing this !

• amazing solution, thanks a lot!

• This post is deleted!

• I'd like to help explain this great algorithm. :-O

This divide-and-conquer 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'`, and `s[i-1,i+1]` is a palindrome "aba":

``````.......aba...
|<-X->| ^
|<---Y-->|
``````

And we know the least cuts for `s[0,i-1)` is X, then the least cuts for `s[0,i+1]` Y is not greater than X+1. Last, we need to find out all the palindromes in `s[0,i+1]` so as to minimize the number of cuts.

• Thank you for sharing. Very elegant solution.

• This post is deleted!