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 1:
Input: s = "aab"
Output: 1
Explanation: The palindrome partitioning ["aa","b"] could be produced using 1 cut.
Example 2:
Input: s = "a"
Output: 0
Example 3:
Input: s = "ab"
Output: 1
Constraints:
1 <= s.length <= 2000
s consists of lower-case English letters only.
Solution:
class Solution {
Boolean[][] dp;
Integer[] dp2;
public int minCut(String s) {
char[] arr = s.toCharArray();
int res = arr.length - 1;
dp = new Boolean[arr.length][arr.length];
dp2 = new Integer[arr.length];
if (isP(arr, 0, arr.length - 1)) return 0;
for (int i = 0; i < arr.length - 1; i ++) {
if (isP(arr, 0, i)) {
res = Math.min(res, 1 + helper(arr, i + 1));
// System.out.println(s.substring(0, i + 1) + ", " + res);
}
}
return res;
}
private int helper(char[] arr, int start) {
if (start == arr.length) return 0;
if (isP(arr, start, arr.length - 1)) return 0;
if (dp2[start] != null) return dp2[start];
int res = arr.length - 1 - start;
for (int i = start; i < arr.length; i ++) {
if (isP(arr, start, i)) {
res = Math.min(res, 1 + helper(arr, i + 1));
}
}
return dp2[start] = res;
}
private boolean isP(char[] arr, int s, int e) {
if (dp[s][e] != null) return dp[s][e];
while (s < e) {
if (arr[s] != arr[e]) {
return dp[s][e] = false;
}
s ++;
e --;
}
return dp[s][e] = true;
}
}