Easiest Java DP Solution (97.36%)


  • 91

    This can be solved by two points:

    1. cut[i] is the minimum of cut[j - 1] + 1 (j <= i), if [j, i] is palindrome.
    2. If [j, i] is palindrome, [j + 1, i - 1] is palindrome, and c[j] == c[i].

    The 2nd point reminds us of using dp (caching).

    a   b   a   |   c  c
                    j  i
           j-1  |  [j, i] is palindrome
       cut(j-1) +  1
    

    Hope it helps!

    public int minCut(String s) {
        char[] c = s.toCharArray();
        int n = c.length;
        int[] cut = new int[n];
        boolean[][] pal = new boolean[n][n];
        
        for(int i = 0; i < n; i++) {
            int min = i;
            for(int j = 0; j <= i; j++) {
                if(c[j] == c[i] && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
                    pal[j][i] = true;  
                    min = j == 0 ? 0 : Math.min(min, cut[j - 1] + 1);
                }
            }
            cut[i] = min;
        }
        return cut[n - 1];
    }

  • 0
    D

    I got exactly same code as yours, except that here I use

    (j + 1 >= i - 1)
    

    and this increases total time largely from 12ms to 32ms.

    Could anyone please help explain that?


  • 1

    Sounds like a typical branch prediction issue to me, but why would it happen here? I am at a loss. It's not like the condition changes randomly on each iteration.


  • 0
    C

    one guess is <= means smaller or equal, it's two comparisons while < is only one. Imagine how you are going to translate it into compiler.


  • 1

    Not likely. a <= b is probably translated as sub a, b; jle ..., a < b is sub a, b; jl .... While technically jle is SF <> OF || ZF == 0 and jl is just SF <> OF, but it's one machine instruction either way and should be blazingly fast unless you hit branch prediction problems because that is what makes these instructions slow, not the actual comparison.


  • 0
    D

    I think your solution is very easy to understand. Just to make sure, the runtime is O(n^2) right? Thanks.


  • 0

    @D_shaw Actually that's just a LeetCode server issue.

    Sometimes it's 30+, sometimes it's 10+.

    Well, this kind of small wave always happens. Not a big issue.


  • 0
    G

    It's a very neat solution, but it uses O(n^2) space, isn't it?


Log in to reply
 

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