Cacher is the code snippet organizer for pro developers

/**
 * 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.
 */
 
public class Solution {
    public int minCut(String s) {
        int len = s.length();
        int[] dp = new int[len + 1];
        boolean[][] isPa = new boolean[len][len];
        for(int i = 0; i <= len; i++){
            dp[i] = len - i;
        }
        for(int i = 0; i < len; i++){
            isPa[i][i] = true;
        }
        for(int i = len - 1; i >= 0; i--){
            for(int j = i; j < len; j++){
                if((s.charAt(i) == s.charAt(j)) && ( j - i < 2 || isPa[i + 1][j - 1])){
                    isPa[i][j] = true;
                    dp[i] = Math.min(dp[i], dp[j + 1] + 1);
                }
            }
        }
        return dp[0] - 1;
    }
}

/**
 * Given a string s, partition s such that every substring of the partition is a palindrome.
 * Return all possible palindrome partitioning of s.
 * For example, given s = "aab",
 * Return
 *  [
        ["aa","b"],
        ["a","a","b"]
    ]
 */

public class Solution {
    public ArrayList<ArrayList<String>> partition(String s) {
        ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
        if(s == null || s.length() == 0)
            return res;
        boolean[][] isPa = new boolean[s.length()][s.length()];
        // single-char word is a palindrome. 
        for(int i = 0; i < s.length(); i++){
            isPa[i][i] = true;
        }
        for(int i = s.length() - 1; i >= 0; i--){
            for(int j = i; j < s.length(); j++){
                if((s.charAt(i) == s.charAt(j)) && ( j - i < 2 || isPa[i + 1][j - 1])){
                    isPa[i][j] = true;
                }
            }
        return partitionHelper(s, 0, isPa);
    }
    public ArrayList<ArrayList<String>> partitionHelper(String s, int start, boolean[][] isPa){
        ArrayList<ArrayList<String>> pa = new ArrayList<ArrayList<String>>();
        if(s.length() == start){
            // backtracking start
            pa.add(new ArrayList<String>());
            return pa;
        }
        for(int i = start; i < s.length(); i++){
            if(isPa[start][i]){
                for(ArrayList<String> subPa : partitionHelper(s, i + 1, isPa)){
                    subPa.add(0, s.substring(start, i + 1));
                    pa.add(subPa);
                }
            }
        }
        return pa;
    }
}