**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.

 1 public class Solution {
 2     private boolean isPalindrome(String s, int start, int end) {
 3         for (int i = start, j = end; i < j; i++, j--) {
 4             if (s.charAt(i) != s.charAt(j)) {
 5                 return false;
 6             }
 7         }
 8         return true;
 9     }
10 
11     private boolean[][] getIsPalindrome(String s) {
12         boolean[][] isPalindrome = new boolean[s.length()][s.length()];
13 
14         for (int i = 0; i < s.length(); i++) {
15             isPalindrome[i][i] = true;
16         }
17         for (int i = 0; i < s.length() - 1; i++) {
18             isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
19         }
20 
21         for (int length = 2; length < s.length(); length++) {
22             for (int start = 0; start + length < s.length(); start++) {
23                 isPalindrome[start][start + length]
24                     = isPalindrome[start + 1][start + length - 1] && s.charAt(start) == s.charAt(start + length);
25             }
26         }
27 
28         return isPalindrome;
29     }
30 
31     public int minCut(String s) {
32         if (s == null || s.length() == 0) {
33             return 0;
34         }
35 
36         // preparation
37         boolean[][] isPalindrome = getIsPalindrome(s);
38         
39         // initialize
40         int[] f = new int[s.length() + 1];
41         for (int i = 0; i <= s.length(); i++) {
42             f[i] = i - 1;
43         }
44         
45         // main
46         for (int i = 1; i <= s.length(); i++) {
47             for (int j = 0; j < i; j++) {
48                 if (isPalindrome[j][i - 1]) {
49                     f[i] = Math.min(f[i], f[j] + 1);
50                 }
51             }
52         }
53 
54         return f[s.length()];
55     }
56 }

reference： http://www.jiuzhang.com/solutions/palindrome-partitioning-ii/