Palindrome Partitioning II | Leetcode

Given a string s, partition s such that every substring of the partition is a palindrome.

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

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

---

Solution: This is a 1D dynamic programming problem. One additional trick is to cache the substring palindrome check in a 2D matrix so that we do not have to recompute that multiple times over.

The DP formula is:

f(i) = 0 : if substring from 0 to i is a palindrome
       min(f[j] + 1) : where j = 0 to i - 1, if substring from j + 1 to i is a palindrome

The answer is then taken from f(len(s) - 1).

Reference: http://yucoding.blogspot.com/2013/08/leetcode-question-133-palindrome.html

public class Solution {
    public int minCut(String s) {
        // Cache palindrome evaluation matrix.
        boolean[][] isPalindrome = new boolean[s.length()][s.length()];
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i; j < s.length(); j++) {
                isPalindrome[i][j] = (s.charAt(i) == s.charAt(j))
                        && (((j - i) <= 1) || isPalindrome[i + 1][j - 1]);
            }
        }
        
        // Dynamic programming loop.
        int[] numCuts = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if (isPalindrome[0][i]) {
                numCuts[i] = 0;
                continue;
            }
            numCuts[i] = s.length();
            for (int j = 0; j < i; j++) {
                if (isPalindrome[j + 1][i]) {
                    numCuts[i] = Math.min(numCuts[i], numCuts[j] + 1);
                }
            }
        }
        
        return numCuts[s.length() - 1];
    }
}