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.
Example:
Input: "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
class Solution {
public int minCut(String s) {
// validate input
if (s == null || s.length() <= 1) {
return 0;
}
// dp
int N = s.length();
// dp[i] -> min number of cuts upto i-index substring with last palindrome
// ending at ith index
int[] dp = new int[N];
// Worst case for each substring
for (int i = 0; i < N; i++)
dp[i] = i;
for (int mid = 1; mid < N; mid++) { // iterate through all chars as mid point of palindrome
// CASE 1. odd len: center is at index mid, expand on both sides
for (int start = mid, end = mid; start >= 0 && end < N
&& s.charAt(start) == s.charAt(end); start--, end++) {
int newCutAtEnd = (start == 0) ? 0 : dp[start - 1] + 1;
dp[end] = Math.min(dp[end], newCutAtEnd);
}
// CASE 2: even len: center is between [mid-1,mid], expand on both sides
for (int start = mid - 1, end = mid; start >= 0 && end < N
&& s.charAt(start) == s.charAt(end); start--, end++) {
int newCutAtEnd = (start == 0) ? 0 : dp[start - 1] + 1;
dp[end] = Math.min(dp[end], newCutAtEnd);
}
}
return dp[N - 1];
}
}