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.     }
  7.     int n = s.length();
  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);
  13.     // res[i] represents the minimum cut needed
  14.     // from s[0] to s[i]
  15.     int[] res = new int[n];
  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;
  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.       }
  29.       res[j] = cut;
  30.     }
  32.     return res[n - 1];
  33.   }
  35.   boolean[][] buildMatrix(String s, int n) {
  36.     boolean[][] dp = new boolean[n][n];
  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.     }
  46.     return dp;
  47.   }
  48. }