-
Notifications
You must be signed in to change notification settings - Fork 4
/
132_minCut.java
61 lines (55 loc) · 1.83 KB
/
132_minCut.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
//O(n) space!!
//O(n^2) time!!!
public class Solution {
public int minCut(String s) {
if(s == null || s.length() <= 1) return 0;
int len = s.length();
int[] dp = new int[len+1];
for(int i = 0; i <= len; i++){
dp[i] = i-1; // initial to current char numbers -1 as the most cut
}
for(int i = 0; i < len; i++){
for(int j = 0; i-j>=0 && i+j<len && s.charAt(i-j) == s.charAt(i+j); j++){ //Even check
dp[i+j+1] = Math.min(dp[i+j+1], 1+dp[i-j]);
}
for(int j = 1; i-j+1>=0 && i+j<len && s.charAt(i-j+1) == s.charAt(i+j); j++){ //Odd check
dp[i+j+1] = Math.min(dp[i+j+1], 1+dp[i-j+1]);
}
}
return dp[len];
}
}
//代码本身没啥问题,但是碰到了TLE。。。。
//这个输入没法handle:无数个a的情况。
//aaaaa.....aaaa
public class Solution {
public int minCut(String s) {
if(s == null || s.length()<= 1) return 0;
int len = s.length();
int[] dp = new int[len+1];
Arrays.fill(dp,-1);
dp[0] = 0;
for(int j = 1; j <= len;j++){
for(int i = 0; i < j; i++){
String str = s.substring(i,j);
if(dp[i]!=-1 && isPalidrome(str)){
if(dp[j] == -1) dp[j] = dp[i]+1;
else dp[j] = Math.min(dp[i]+1, dp[j]);
}
}
}
return dp[len]-1; //Attention, this is cut number, not how many palidromes we can cut.
}
public boolean isPalidrome(String s){
if(s == null) return false;
if(s.length()<= 1) return true;
int i = 0;
int j = s.length()-1;
while(i<j){
if(s.charAt(i)!=s.charAt(j)) return false;
i++;
j--;
}
return true;
}
}