Palindrome Partitioning II

Given a string s, cut s into some substrings such that every substring is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

Example Given s = "aab",

Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.

Notes:

1. Sequence DP
2. State: f[i], the minimum cut number from 0 to i
3. Function: f[i+1] = MIN(f[j]) when s(j...i) is palindrome, j is from 0 to i
4. Initialize: f[0] = -1
5. Answer: f[n]

Improve, Sequence DP + Interval DP

1. State: f[i], the minimum cut number from 0 to i. p[i][j] represents from i to j is palindrome or not
2. Function: f[i+1] = MIN(f[j]) when p[i][j] == true, j is from 0 to i. p[j][i] = true when s[i] == s[j] && i-j < 2 || p[j+1][i-1] == true
3. Initialize: f[0] = -1
4. Answer: f[n]

    public int minCut(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        // state
        int n = s.length();
        int[] f = new int[n+1];

        // initialize
        f[0] = -1;

        // function
        for(int i = 0; i < n; ++i) {
            f[i+1] = f[i]+1;
            for (int j = i; j >= 0; --j) {
                if (isPalindrome(s.substring(j, i+1))) {
                    f[i+1] = Math.min(f[i+1], f[j]+1);
                }
            }
        }

        // answer
        return f[n];
    }

    private boolean isPalindrome(String s) {
        if (s.length() <= 1) {
            return true;
        }

        int i = 0;
        int j = s.length()-1;

        while(i <= j) {
            if (s.charAt(i++) != s.charAt(j--)) {
                return false;
            }
        }

        return true;
    }

    public int minCut(String s) {
        if (s == null || s.isEmpty()) {
            return 0;
        }

        // state
        int n = s.length();
        int[] f = new int[n+1];
        boolean[][] p = new boolean[n][n];

        // initialize
        f[0] = -1;

        // function
        for(int i = 0; i < n; ++i) {
            f[i+1] = f[i]+1;
            for (int j = i; j >= 0; --j) {
                if (s.charAt(i) == s.charAt(j) && (i-j < 2 || p[j+1][i-1])) {
                    p[j][i] = true;
                    f[i+1] = Math.min(f[i+1], f[j]+1);
                }
            }
        }

        // answer
        return f[n];
    }