https://oj.leetcode.com/problems/palindrome-partitioning-ii/

LeetCode_PalindromePartitioningII.java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * Created by benjamin on 10/21/14.
 */
public class PalindromePartitioningII {
  public int minCut(String s) {
    if (s.length() <= 1) {
      return 0;
    }
    boolean[][] palindromes = new boolean[s.length()][s.length()];
    for (int gap = 0; gap < s.length(); gap++) {
      for (int i = 0; i < s.length() - gap; i++) {
        int j = i + gap;
        if (i == j
            || (j == i + 1 && s.charAt(i) == s.charAt(j))
            || (palindromes[i + 1][j - 1] && s.charAt(i) == s.charAt(j))) {
          palindromes[i][j] = true;
        } else {
          palindromes[i][j] = false;
        }
      }
    }
    int[] cuts = new int[s.length() + 1];
    cuts[0] = -1; cuts[1] = 0;
    for (int i = 2; i < cuts.length; i++) {
      int min = s.length();
      for (int j = 0; j < i; j++) {
        if (palindromes[j][i - 1]) {
          min = Math.min(min, cuts[j] + 1);
        }
      }
      cuts[i] = min;
    }
    return cuts[s.length()];
  }

  public static void main(String[] args) {
    PalindromePartitioningII pp = new PalindromePartitioningII();
    System.out.println(pp.minCut("aab"));
  }
}