Palindrome Partitioning II 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.

gistfile1.java

public class Solution {
    private HashMap<String, Boolean> palindromeCache;
    private HashMap<String, Integer> resultCache;
    public int minCut(String s) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        palindromeCache = new HashMap<String, Boolean>();
        resultCache = new HashMap<String, Integer>();
        return minCutRecursive(s);
    }
    
    public int minCutRecursive(String s) {
        if (resultCache.containsKey(s)) {
            return resultCache.get(s);
        }
        if (isParlindrome(s)) {
            return 0;
        }
        int min = s.length();

        for (int i = s.length() - 1; i > 0; i--) {
            String postfix = s.substring(i);
            if (isParlindrome(postfix)) {
                int curCut = minCutRecursive(s.substring(0, i)) + 1;
                if (curCut < min) {
                    min = curCut;
                }
            }
        }
        resultCache.put(s, min);
        return min;
    }
    
    public boolean isParlindrome(String s) {
        if (s.length() == 0) {
            return false;
        } else if (s.length() == 1) {
            return true;
        }else if (palindromeCache.containsKey(s)) {
            return palindromeCache.get(s);
        }else {
            int left = 0, right = s.length() - 1;
            boolean result = s.charAt(left) == s.charAt(right) && isParlindrome(s.substring(left + 1, right));
            palindromeCache.put(s, result);
            return result;
        }
    }
}