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


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

  • 1
    E

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


  • 2
    D

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


  • 1
    T

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


  • 0
    L

    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!


  • 0
    Z

    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


  • 0
    M

    best ever ! thanks so mcuh


  • 0

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


  • 1
    P

    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.


  • 0
    T
    This post is deleted!

  • 26
    D

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

  • 0
    P

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


  • 0
    W

    amazing solution, thanks a lot!


  • 0
    F
    This post is deleted!

  • 63
    J

    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.


  • 0
    P

    Thank you for sharing. Very elegant solution.


  • -20
    H
    This post is deleted!

  • -8
    H

    learn more about java visit here http://thatsjavainfo.com


  • 1
    L

    Amazing Algorithm ~~~~


  • 1
    B

    this is not divide and conquer. This is DP.
    looking backwards of what he is doing, he is building the right cut K[i] for all i<n. aid K[n] is min(all valid palindrome(j,n) + K[j]). However , he did it in a very elegant , serial way


Log in to reply
 

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