Given a string s, cut s into some substrings such that every substring is a palindrome.
Return the minimum cuts needed for a palindrome partitioning of s.
Given s = "aab",
Return 1 since the palindrome partitioning ["aa", "b"] could be produced using 1 cut.
For this problem, the minimum cuts to achieve all single palindrome words could be defined as f[n]. To solve this problem, the dynamic programming is needed to be used. For any integer from 0 to i-1, the f[i] is depend on the minimum value of f[j] + 1 becuase if there any value less than it will update it.
public class Solution {
/**
* @param s a string
* @return an integer
*/
public int minCut(String s) {
if (s==null || s.length() == 0 ) {
return 0;
}
int n = s.length();
//preprocessing to store all the sub-string's boolean palindrome feature
boolean[][] isPalindrome = getIsPalindorme(s);
int[] f = new int[n+1];
//initialize
for (int i =0; i <= n; i++) {
f[i] = i-1;
}
//DP
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++ ) {
if (isPalindrome[j][i-1]) {
f[i] = Math.min(f[i],f[j]+1);
}
}
}
return f[n];
}
//this method is used to preprocess the result whether it is a panlindrome string of
//the certain substring from index i to index j and store them all into a matrix
public boolean[][] getIsPalindorme(String s) {
int length = s.length();
boolean [][] isPalindrome = new boolean[length][length];
//initialize for all single characters
for (int i = 0; i < length; i++) {
//this means all the single character in the string could be used as
//a palindrome word
isPalindrome[i][i] = true;
}
//initialize for all two neighbor characters
for (int i = 0; i < length-1; i++) {
isPalindrome[i][i + 1] = (s.charAt(i) == s.charAt(i + 1));
}
//develop for all result from start to start + lengthj indexs subtring
for (int delta = 2; delta <= length -1; delta++) {
for (int start = 0; start + delta < length; start++) {
//the result of the string from index start to start+length
//is based on the result of string with index start+1 to start+length-1
//and and the two chars at start indexa and start +length index are equal
isPalindrome[start][start + delta]
= isPalindrome[start + 1][start + delta - 1] && s.charAt(start) == s.charAt(start + delta);
}
}
return isPalindrome;
}
}