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.
Solution:
1. public class Solution {
2. public int minCut(String s) {
3. if (s == null || s.length() == 0) {
4. return 0;
5. }
6. 7. int n = s.length();
8. 9. // build the dp matrix to hold the palindrome information
10. // dp[i][j] represents whether s[i] to s[j] can form a palindrome
11. boolean[][] dp = buildMatrix(s, n);
12. 13. // res[i] represents the minimum cut needed
14. // from s[0] to s[i]
15. int[] res = new int[n];
16. 17. for (int j = 0; j < n; j++) {
18. // by default we need j cut from s[0] to s[j]
19. int cut = j;
20. 21. for (int i = 0; i <= j; i++) {
22. if (dp[i][j]) {
23. // s[i] to s[j] is a palindrome
24. // try to update the cut with res[i - 1]
25. cut = Math.min(cut, i == 0 ? 0 : res[i - 1] + 1);
26. }
27. }
28. 29. res[j] = cut;
30. }
31. 32. return res[n - 1];
33. }
34. 35. boolean[][] buildMatrix(String s, int n) {
36. boolean[][] dp = new boolean[n][n];
37. 38. for (int i = n - 1; i >= 0; i--) {
39. for (int j = i; j < n; j++) {
40. if (s.charAt(i) == s.charAt(j) && (j - i <= 2 || dp[i + 1][j - 1])) {
41. dp[i][j] = true;
42. }
43. }
44. }
45. 46. return dp;
47. }
48. }