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.

DP问题，网上看到的最好的解释：

http://www.lifeincode.net/programming/leetcode-palindrome-partitioning-i-and-iijava/

In this problem, we often needs to check if the substring(i, j) of the original string is palindrome or not. So we need to save this very important information to an array to prevent checking a same substring for several times. This is a 2-D boolean array which is quite easy to generate. We can generate it from short length to long length. When s.charAt(i) is equal to s.charAt(j), if the array isPalindrome[i + 1][j – 1] is true, then we can update isPalindrome[i][j] = true.

In the previous problem, we can use recursive function to generate all possible string lists.

In this problem, if we use recursive solution, we will got TLE. So a DP solution is needed. We can use a 1-D array D[n] to save the minimum cut. For example, D[i] saves the number of minimum cut of substring(i, n). We can start from i = n – 1, and move i from right to left. When we want to get the D[i] for a new i, we can check every possible substrings from i to n, which means we can use another point j, in which j is between i and n. If substring(i, j) is a palindrome, then we can update D[i] = min(D[i], 1 + D[j + 1]).

This method can also be used in the first problem to save more time.

public class Solution {
public int minCut(String s) {
int n = s.length();
boolean[][] isPalindrome = new boolean[n][n];
for (int i = 0; i < n; i++)
isPalindrome[i][i] = true;
for (int i = n - 1; i >= 0; i--) {
for (int j = i + 1; j < n; j++) {
if (s.charAt(i) == s.charAt(j)) {
if (j - i < 2 || isPalindrome[i + 1][j - 1])
isPalindrome[i][j] = true;
}
}
}
int[] minCut = new int[n + 1];
for (int i = n; i >= 0; i--)
minCut[i] = n - 1 - i;
for (int i = n - 1; i >= 0; i--) {
for (int j = i; j < n; j++) {
if (isPalindrome[i][j]) {
minCut[i] = Math.min(minCut[i], 1 + minCut[j + 1]);
}
}
}
return minCut[0];
}
}

### Like this:

Like Loading...

*Related*