h******3
发帖数: 351 | 1 complain runtime error
Last executed input
"a"
public int minCut(String s){
int count = 0;
ArrayList> res = partition(s);
for(ArrayList subpa : res)
count += subpa.size();
return count;
}
public ArrayList> partition(String s) {
if(s == null || s.length() == 0)
return new ArrayList>();
boolean[][] isPa = new boolean[s.length()][s.length()];
for(int i = 0; i < s.length(); i++){
isPa[i][i] = true;
}
for(int i = s.length() - 2; i >= 0; i --){
isPa[i][i + 1] = s.charAt(i) == s.charAt(i + 1);
for(int j = i + 2; j < s.length(); j++)
isPa[i][j] = (s.charAt(i) == s.charAt(j)) && isPa[i + 1][j - 1];
}
return partitionHelper(s, 0, isPa);
}
public ArrayList> partitionHelper(String s, int start,
boolean[][] isPa){
ArrayList> pa = new ArrayList>();
if(start == s.length()){
pa.add(new ArrayList());
return pa;
}
for(int i = start; i < s.length(); i++){
if(isPa[start][i])
for(ArrayList subPa: partitionHelper(s, i + 1, isPa)){
subPa.add(0, s.substring(start, i + 1));
pa.add(subPa);
}
}
return pa;
} |
|
