132. Palindrome Partitioning II - pangeneral/leetcode-notebook GitHub Wiki

The basic idea is using two dp arrays:

1. isPalindrome[i][j] to record whether s[i, j] is palindrome and
2. num[i] to record the minimum cut for s[0, i].

Here, s[i, j] is the abbreviation for s.substring(i, j + 1).

Traverse the array to calculate num and isPalindrome. num[s.length() - 1] is the result we want. Note that if s[0, i] is palindrome then num[i] equals to zero because we don't need to cut it to get the sequence of palindrome.

public int minCut(String s) {
    char str[] = s.toCharArray();
    boolean isPalindrome[][] = new boolean[s.length()][s.length()];
    int num[] = new int[s.length()];

    for(int i = 0; i < s.length(); i++) {
        int min = Integer.MAX_VALUE;
        for(int j = 0; j <= i; j++) {
            if( str[i] == str[j] && (j + 1 >= i || isPalindrome[j + 1][i - 1]) ){
                isPalindrome[j][i] = true;
                min = j == 0 ? 0 : Math.min(min, num[j - 1] + 1);
            }
        }
        num[i] = min;
    }
    return num[s.length() - 1];
}