leetcode 132
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.
Solution. At the beginning, I tried to use DFS and recursion way. But both of them got TLE. This problem is actually can be solved in O(n^2) time. I learned from here.
This can be treated as 1-dimension dp problem. Let’s define array cut[]. cut[j] is the minimum cut of s[0…j]. Ok, then we can calculate cut[j] from cut[j – 1]. Let’s say the position i before j. If s[i…j] is palindrome, the cut[j] = min{cut[[j], cut[i – 1] + 1}.
Like below one, cut[6] = min{cut[6], cut[2] + 1}.
In order to check if s[i…j] is palindrome. We need a boolean dp[][] array, can check if s[i] == s[j] and d[[i + 1…j – 1] == true.
// dp solution. O(n^2) time complexity
public static int minCut(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int[] cut = new int[s.length()];
Arrays.fill(cut, Integer.MAX_VALUE);
for (int j = 0; j < cut.length; j++) {
for (int i = 0; i <= j; i++) {
// check dp[i][j]. when i + 1 >= j this is for checking length less than or eqaul to 2. such as 'a', 'ab'
dp[i][j] = s.charAt(i) == s.charAt(j) && (i + 1 >= j || dp[i + 1][j - 1]);
if (dp[i][j]) {
// when i == 0, it means whole s[0...j] is a palindrome.
cut[j] = Math.min(cut[j], i == 0 ? 0 : cut[i - 1] + 1);
}
}
}
return cut[dp.length - 1];
}
Check my code on github.