这道题目我采用了 divide and conquer + DP
但是超时了。先上我的code
My code:
public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[][] cache = new int[n][n];
initialize(s, cache);
return helper(0, n - 1, s, cache);
}
private int helper(int left, int right, String s, int[][] cache) {
if (cache[left][right] >= 0) {
return cache[left][right];
}
else {
int ans = Integer.MAX_VALUE;
for (int i = left; i < right; i++) {
ans = Math.min(ans, 1 + helper(left, i, s, cache) + helper(i + 1, right, s, cache));
if (ans == 1) {
break;
}
}
cache[left][right] = ans;
return ans;
}
}
private void initialize(String s, int[][] cache) {
int n = cache.length;
for (int i = 0; i < n; i++) {
cache[i][i] = 0;
int begin = i - 1;
int end = i + 1;
while (begin >= 0 && end < n) {
if (cache[begin + 1][end - 1] == -2) {
cache[begin][end] = -2;
}
else if (s.charAt(begin) != s.charAt(end)) {
cache[begin][end] = -2;
}
else {
cache[begin][end] = 0;
}
begin--;
end++;
}
begin = i;
end = i + 1;
while (begin >= 0 && end < n) {
if (begin + 1 <= end - 1 && cache[begin + 1][end - 1] == -2) {
cache[begin][end] = -2;
}
else if (s.charAt(begin) != s.charAt(end)) {
cache[begin][end] = -2;
}
else {
cache[begin][end] = 0;
}
begin--;
end++;
}
}
}
public static void main(String[] args) {
Solution test = new Solution();
String s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
int ret = test.minCut(s);
System.out.println(ret);
}
}
recursion DP + divide and conquer
我采取了多种cache策略 和剪枝
将 string s 彻底扫描一遍，
cache[i][j] = -2 -> not palindrome
cache[i][j] = 0 -> is panlindrome
耗时： O(n^2)当 left +1 == right and s[left, right] 非 palindrome 时，直接返回1，只能一刀切，没必要继续recursion
重量级剪枝
当 ans = 1 时，没必要继续剪枝，这一定是最小cut。直接break
采取了这些策略后，速度快了很多。
但还是 TLE
这个例子：
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我写程序测试了下，跑的时间是，200ms。我同学的iteration 时间是，27ms
我在想，为什么会满这么多呢！！明明已经精简到极限了啊！
后来测试了下，栈的长度。
我的整个recursion 过程，栈的个数达到了 4000万 + 个！！
光凭这些入栈出栈的操作，就会浪费大量的时间！
而 iteration dp, 却没有这些事，所以速度更快。
于是开始考虑 iteration 做法。
My code:
public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int n = s.length();
int[] mcut = new int[n];
boolean[][] pal = new boolean[n][n];
initialize(pal, s);
for (int i = 1; i < n; i++) {
if (pal[0][i]) {
mcut[i] = 0;
}
else {
int min = mcut[i - 1] + 1;
for (int j = i - 1; j >= 1; j--) {
if (pal[j][i]) {
min = Math.min(min, mcut[j - 1] + 1);
}
}
mcut[i] = min;
}
}
return mcut[n - 1];
}
private void initialize(boolean[][] pal, String s) {
for (int i = 0; i < s.length(); i++) {
int begin = i;
int end = i;
while (begin >= 0 && end < s.length()) {
if (s.charAt(begin) != s.charAt(end)) {
break;
}
else {
pal[begin][end] = true;
begin--;
end++;
}
}
begin = i;
end = i + 1;
while (begin >= 0 && end < s.length()) {
if (s.charAt(begin) != s.charAt(end)) {
break;
}
else {
pal[begin][end] = true;
begin--;
end++;
}
}
}
}
}
reference:
https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36
iteration DP
int[] mcut[i] 表示 [0, i] 的substring 需要的最小cut数
boolean[][] pal[i][j] 表示 substring [i, j] 是否为 palindrome
s = [0, ..., j] [i, ...]
首先判断 s[0, i] 是否为 palindrome 如果是，直接 mcut[i] = 1
如果不是，则开始循环：
如果 [j, i] 是 palindrom
则 min = Math.min(min, mcut[j - 1] + 1);
以此类推
总结：
昨天做 burst ballon 的时候，就是这种 divide and conquer + DP 解决了问题。今天想如法炮制，没想到还是不行。
究其原因，还是recursion 的栈太多了。得用Iteration
但是recursion + cache 比较容易想，而 iteration DP的推导式太难想了。
Anyway, Good luck, Richardo! -- 08/20/2016
My code:
public class Solution {
public int minCut(String s) {
if (s == null || s.length() == 0) {
return 0;
}
int len = s.length();
int[] cut = new int[len];
boolean[][] pal = new boolean[len][len];
for (int i = 0; i < len; i++) {
int min = i;
for (int j = 0; j <= i; j++) {
if (s.charAt(j) == s.charAt(i) && (j + 1 > i - 1 || pal[j + 1][i - 1])) {
pal[j][i] = true;
min = (j == 0 ? 0 : Math.min(min, cut[j - 1] + 1));
}
}
cut[i] = min;
}
return cut[len - 1];
}
}
reference:
https://discuss.leetcode.com/topic/32575/easiest-java-dp-solution-97-36/2
Anyway, Good luck, Richardo! -- 10/19/2016
