Palindrome Partition
Given a string, a partitioning of the string is a palindrome partitioning if every partition is a palindrome.
For example, “aba |b | bbabb |a| b| aba” is a palindrome partitioning of “ababbbabbababa”.
Determine the fewest cuts needed for palindrome partitioning of a given string.
For example,
minimum 3 cuts are needed for “ababbbabbababa”. The three cuts are “a | babbbab | b | ababa”.
If a string is palindrome, then minimum 0 cuts are needed.
Return the minimum cuts.
Solution: Dp, incremental cuts
Base Case: 0 letters, and 1 letter don't need to be cut
Induction Rule:
Check every increment
Check every cut
if right cut is a palindrome, Check if left cut + 1 is best cut so far
private boolean checkPali(String input, int left, int right){
if (left >= right) return true;
while (right > left){
if (input.charAt(left) != input.charAt(right)){
return false;
}
left++;
right--;
}
return true;
}
public int paliPart(String input){
if(input == null || input.length() <= 1) return 0;
int[] M = new int[input.length() + 1];
M[0] = 0; M[1] = 0;
for (int i = 2; i <= input.length(); i++){ //check every increment
int min = Integer.MAX_VALUE;
for (int j = 0; j < i; j++){ //check every cut
if (checkPali(input, j, i - 1)){
min = j == 0 ? 0 : Math.min(min, M[j] + 1);
}
}
M[i] = min == Integer.MAX_VALUE ? -1 : min;
}
return M[input.length()];
}
Time Complexity: O(N) increment check * O(N) cut check * O(N) checkPali = O(N^3)
Space Complexity: O(N)
0 1 2 3 4 5
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Extra Space Optimization: Memoize palindrome segments
Using O(N^2) space we can track validity of segments.
int[][] paliCheck //is i -> j a palindrome
int[] cuts // min cuts for 0 -> i
Reducing validity check to O(1) means time complexity turns into O(N^2)
Last updated
Was this helpful?