這道題目我采用了 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嘱吗，只能一刀切雇卷，沒必要繼續(xù)recursion
重量級剪枝
當 ans = 1 時洪橘，沒必要繼續(xù)剪枝颠区，這一定是最小cut帚戳。直接break
采取了這些策略后玷或，速度快了很多。
但還是 TLE
這個例子：
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
我寫程序測試了下片任，跑的時間是偏友，200ms。我同學(xué)的iteration 時間是对供，27ms
我在想位他，為什么會滿這么多呢！产场！明明已經(jīng)精簡到極限了岸焖琛！
后來測試了下京景，棧的長度窿冯。
我的整個recursion 過程，棧的個數(shù)達到了 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數(shù)
boolean[][] pal[i][j] 表示 substring [i, j] 是否為 palindrome
s = [0, ..., j] [i, ...]
首先判斷 s[0, i] 是否為 palindrome 如果是较鼓，直接 mcut[i] = 1
如果不是，則開始循環(huán)：
如果 [j, i] 是 palindrom
則 min = Math.min(min, mcut[j - 1] + 1);
以此類推
總結(jié)：
昨天做 burst ballon 的時候，就是這種 divide and conquer + DP 解決了問題博烂。今天想如法炮制香椎，沒想到還是不行。
究其原因禽篱，還是recursion 的棧太多了畜伐。得用Iteration
但是recursion + cache 比較容易想，而 iteration DP的推導(dǎo)式太難想了躺率。
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
