/
Solution.java
executable file
·71 lines (54 loc) · 2.04 KB
/
Solution.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
public class Solution {
public int minCut(String s) {
boolean[][] dp = new boolean[s.length()][s.length()];
int[] mincut = new int[s.length()];
for(int i = 0; i < mincut.length;i++) mincut[i] = Integer.MAX_VALUE;
for(int i = 0; i < s.length(); i++){
for(int j = i; j >= 0; j--){
if(i == j) dp[i][j] = true;
else if(j+1 == i && s.charAt(j) == s.charAt(i)) dp[i][j] = true;
else if(dp[i-1][j+1] && s.charAt(i) == s.charAt(j)) dp[i][j] = true;
if(dp[i][j]){
if(j>0) mincut[i] = Math.min(mincut[i], mincut[j-1]+1);
else mincut[i] = 0;
}
}
}
return mincut[mincut.length-1];
}
}
public class Solution {
public int minCut(String s) {
char[] S = s.toCharArray();
if(S.length == 0) return 0;
boolean[][] P = new boolean[S.length][S.length];
// len 1
Arrays.fill(P[1 - 1], true);
// len 2
for(int i = 0; i < S.length - 1; i++){
P[2 - 1][i] = S[i] == S[i + 2 - 1];
}
// len 3 to max
for(int len = 3; len <= S.length; len++){
for(int i = 0; i < S.length - (len - 1); i++){
P[len - 1][i] = P[len - 1 - 2][i + 1] && S[i] == S[i + len - 1];
}
}
int[] mincut = new int[S.length + 1];
mincut[0] = 0;
mincut[1] = 0;
for(int len = 2; len <= S.length; len++){
if(P[len - 1][0]){
mincut[len] = 0;
}else{
mincut[len] = mincut[len - 1] + 1;
for(int i = 1; i < len - 1; i++){
if(P[len - i - 1][i]){
mincut[len] = Math.min(mincut[i] + 1 , mincut[len]);
}
}
}
}
return mincut[S.length];
}
}