Description
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
DP, time O(n ^ 2), space O(n ^ 2)
用DP就可以做，还需要使用一个额外的二维数组帮助判断substring是否回文，否则O(n ^ 3)的复杂度会TLE。
class Solution {
public int minCut(String s) {
if (s == null || s.length() < 2) {
return 0;
}
int n = s.length();
int[] minCut = new int[n + 1]; // minCut of s.substring(0, j)
boolean[][] isPalin = new boolean[n][n]; // whether s.substring(i, j + 1) is palin
minCut[0] = -1;
for (int i = 1; i <= n; ++i) {
minCut[i] = i - 1; // cut between each character
for (int j = i - 1; j >= 0; --j) {
isPalin[j][i - 1] = s.charAt(j) == s.charAt(i - 1)
&& (i - j <= 3 || isPalin[j + 1][i - 2]);
if (isPalin[j][i - 1]) {
minCut[i] = Math.min(minCut[i], 1 + minCut[j]);
}
}
}
return minCut[n];
}
}
