Version #2 DP - Expand from the center [TODO]
四刷 07/2022
Version #1 DP
写了一个bug就是当i为0的时候是从头切，相当于不用切一刀
Time O(N^2)
Space O(N^2)
Runtime: 85 ms, faster than 53.92% of Java online submissions for Palindrome Partitioning II.
Memory Usage: 48.3 MB, less than 45.73% of Java online submissions for Palindrome Partitioning II.
class Solution {
public int minCut(String s) {
int len = s.length();
boolean[][] isPalin = new boolean[len][len];
int[] dp = new int[len]; // min cut to make substring s[0, i] a valid palindrome partitioning
for (int j = 0; j < len; j++) {
// 0 1
dp[j] = j; // cut into single characters
for (int i = j; i >= 0; i--) {
if (i == j) {
isPalin[i][j] = true;
} else if (i + 1 == j) {
isPalin[i][j] = s.charAt(i) == s.charAt(j);
} else {
isPalin[i][j] = s.charAt(i) == s.charAt(j) && isPalin[i + 1][j - 1];
}
// ... [i, j] j + 1
if (isPalin[i][j]) {
dp[j] = Math.min(dp[j], (i == 0 ? 0 : 1 + dp[i - 1]));
}
}
}
return dp[len - 1];
}
}
三刷 06/2022
Version #1 DP - Expand 1 index
写了一个bug就是当start + 1 >= end - 1的状态是在dp里面搜不到的，需要特殊处理
Time O(N^2)
Space O(N^2)
Runtime: 45 ms, faster than 66.23% of Java online submissions for Palindrome Partitioning II.
Memory Usage: 48.2 MB, less than 50.29% of Java online submissions for Palindrome Partitioning II.
class Solution {
public int minCut(String s) {
int len = s.length();
// dp[i] - min cuts to partition substring [0, i)
int[] dp = new int[len + 1];
boolean[][] palindromeMem = new boolean[len + 1][len + 1];
for (int i = 1; i <= s.length(); i++) {
dp[i] = Integer.MAX_VALUE;
for (int j = i - 1; j >= 0; j--) {
// If substring [j, i) is palindrome, then we can update min
if (isPalindrome(s, j, i - 1, palindromeMem)) {
// System.out.printf("j=%d, i-1=%d, dp[j]=%d\n", j, i - 1, dp[j]);
dp[i] = Math.min(dp[i], dp[j] + (j == 0 ? 0 : 1));
}
}
// System.out.printf("dp[%d]=%d\n", i, dp[i]);
}
return dp[s.length()];
}
private boolean isPalindrome(String s, int start, int end, boolean[][] palindromeMem) {
if (start >= end) {
palindromeMem[start][end] = true;
return true;
}
// start . end
palindromeMem[start][end] = s.charAt(start) == s.charAt(end) && (start + 1 >= end - 1 || palindromeMem[start + 1][end - 1]);
return palindromeMem[start][end];
}
}
2ND TRY
The solution below is better
49.96 %
class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
// min[k] -> min cut we need to make [0, k] valid
int[] min = new int[len];
boolean[][] isPalindrome = new boolean[len][len];
for (int i = 0; i < len; i++) {
isPalindrome[i][i] = true;
}
//min[0] = 0;
// min[j] = Math.min(min[j - 1] + 1, Math.min(min[i - 1] + 1 && isPalindrome(i, j))
isPalindrome[0][0] = true;
for (int j = 1; j < len; j++) {
min[j] = min[j - 1] + 1; // i == j
for (int i = j - 1; i >= 0; i--) {
isPalindrome[i][j] = checkPalindrome(s, i, j, isPalindrome);
if (isPalindrome[i][j]) {
min[j] = Math.min(min[j], (i - 1 >= 0 ? min[i - 1] : -1) + 1);
}
}
}
return min[len - 1];
}
private boolean checkPalindrome(String s, int i, int j, boolean[][] isPalindrome) {
if (i >= j) {
return true;
}
// ij
// a b a
if (s.charAt(i) == s.charAt(j)) {
if (j == i + 1 || isPalindrome[i + 1][j - 1]) {
return true;
}
}
return false;
}
}
1ST TRY
68.97 %
public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) return 0;
char[] array = s.toCharArray();
int length = s.length();
//minCut ends with index i
int[] dp = new int[length];
boolean[][] isPalindrome = new boolean[length][length];
for (int right = 0; right < length; right++) {
int min = right;
for (int left = 0; left <= right; left++) {
if (array[left] == array[right] && (left + 1 >= right - 1 || isPalindrome[left + 1][right - 1])) {
isPalindrome[left][right] = true;
min = left == 0 ? 0 : Math.min(min, dp[left - 1] + 1);
}
}
dp[right] = min;
}
return dp[length - 1];
}
}
No comments:
Post a Comment