Palindrome Partitioning I & II

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"]
  ]

The first problem is a typical backtracking problem. Start from index 0. We check each substring, and recursively check the next substring, until we reach the end of the string. If we successfully add all substrings into the partition list, we can add this partition to the rst list.

For example: s = "aab"

start = 0

check substring(0, 1) -> (1, 2) -> (2, 3) -> add

remove (2, 3)

(0, 1) -> (1, 3) not palindrome

(0, 2) -> (2, 3) -> add

public class PalindromePartition {
    public ArrayList> partition(String s) {
        if (s == null)
            throw new NullPointerException("Null string!");
        ArrayList> rst = new ArrayList> ();
        if (s.length() == 0)
            return rst;
        partitionString(s, rst, new ArrayList (), 0);
        return rst;
       
    }
    private void partitionString (String s, ArrayList> rst, ArrayList partition, int start) {
        if (start == s.length()) {
            rst.add(new ArrayList (partition));
            return;
        }
        for (int i = start + 1; i <= s.length(); i++) {
            String tmp = s.substring(start, i);
            if (!isPalindrome(tmp))
                continue;
            partition.add(tmp);
            partitionString(s, rst, partition, i);
            partition.remove(partition.size() - 1);
        }
    }
    private boolean isPalindrome(String s) {
        int start = 0;
        int end = s.length() - 1;
        while (start < end) {
            if (s.charAt(start) != s.charAt(end))
                return false;
            start++;
            end--;
        }
        return true;
    }
    
}

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.

I am definitely not good at DP, especially when I need to it.. twice...

This problem is obviously a typical DP (when it comes to find the maximum or minimum, you probably want to start your approach of DP first).

I like to show things using examples, mainly because I am not at describing things.

s = "abbab"
        s.charAt(i)             0  1  2  3  4
        s                             a  b  b  a  b
possible places to cut: 0  1  2  3  4  5

So I define an array cut[s.length() + 1]. cut[i] is aimed to store the minimum cut needed for s.substring(0, i).
cut[0] =  0, obviously, empty string.
cut[1] = 0, because s.substring(0,1) is a palindrome (single character).
start from cut[2]:
    1. if s.substring(0, i) is a palindrome, cut[i] = 0;
    2. otherwise, if s.substring(start,i) (start = 1, ... i - 1) is a palindrome, cut[i] = cut[start] + 1;
return cut[s.length], which is cut[5] in this case.

The next part is, how to check if s.substring(start, end) is a palindrome. Of course we can do it iteratively, but is it more convenient if we draw a table of all palindrome substrings of s and just check the table every time?
Yep, that's pretty much the solution.

1. palindrome[i][i] is obviously a palindrome since it only contains one character.
2. palindrome[i][i + 1] is a palindrome if s.charAt(i) == s.charAt(j)
3. palindrome[i][j] is a palindrome if palindrome[i+1][j-1] && s.charAt(i) ==s.charAt(j)

start \ end   0   1   2   3    4
        0        T   F   F   T    F
        1             T   T   T    F
        2                  T    F   T
        3                        T   F
        4                             T

public class PalindromePartition {
    public int minCut(String s) {
        if (s == null || s.length() == 0)
            return 0;
        //**************************************
        // I write this single loop to check if the string itself is a plindrome, 
        //alternatively you can include it into the matrix or write a boolean checkPalindrome (s) method
        int startp = 0;
        int endp = s.length() - 1;
        while (startp < endp)
        {
         if(s.charAt(startp) != s.charAt(endp))
          break;
         startp++;
         endp--;
        }
        if (endp <= startp)
         return 0;
        //****************************************
        int[] cut = new int[s.length() + 1];
        boolean[][] palindromeMatrix = isPalindrome(s);
        cut[0] = 0;
        cut[1] = 0;
        for (int end = 2; end < cut.length; end++)
        {
            cut[end] = Integer.MAX_VALUE;
            if (palindromeMatrix[0][end - 1])
            {
                cut[end] = 0;
                continue;
            }
            for (int start = 1; start < end; start++)
            {
                if (!palindromeMatrix[start][end - 1])
                    continue;
                cut[end] = Math.min(cut[end], cut[start] + 1);
            }
        }
        return cut[s.length()];
    }
    private boolean[][] isPalindrome(String s)
    {
        boolean[][] palindromeMatrix = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++)
            palindromeMatrix[i][i] = true;
        for (int i = 0; i < s.length() - 1; i++)
            palindromeMatrix[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
        for (int length = 3; length < s.length(); length++)
        {
            for (int start = 0; start <= s.length() - length; start++)
                palindromeMatrix[start][start + length - 1] = (palindromeMatrix[start + 1][start + length - 2] && (s.charAt(start) == s.charAt(start + length - 1)));
        }
        return palindromeMatrix;
    }
}