[Java/31ms] A mediocre thinks out an ordinary solution, O(N^2) in space & time.


  • 0

    Gradually updating palindrome table instead of checking palindrome from scratch.

    public int minCut(String s) {
            if (s == null || s.length() == 0)
                return 0;
    
            char[] chs = s.toCharArray();
            int[] dp = new int[s.length()];
            
            boolean[][] is_palindrome = new boolean[chs.length][chs.length];
            for (int i = 0; i < chs.length; i++) {
                int min = i;
                for (int j = 0; j <= i; j++) {
                    if (chs[j] == chs[i]) {
                        if (j >= i-1 || is_palindrome[j+1][i-1])
                        {
                            is_palindrome[j][i] = true;
                            if (j == 0) {
                                min = 0;
                            } else {
                                min = min > dp[j - 1] + 1 ? dp[j - 1] + 1 : min;
                            }
                        }
                    }
                }
                dp[i] = min;
            }
    
            return dp[chs.length-1];
        }
    

Log in to reply
 

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