mm
BAN USERpublic class StringReduction {
StringReduction() {
}
private int allEqual(String str) {
boolean ret = true;
char pc;
if (str.length() == 1)
return 1;
char[] ca = str.toCharArray();
pc = ca[0];
for (int i = 1; i < ca.length; i++) {
if (ca[i] != pc)
return 0;
pc = ca[i];
}
return ca.length;
}
private String replaceTwo(String str, int i) {
if (str == null)
throw new NullPointerException();
if (str.length() == 1)
return str;
if (str.length() - 1 < i + 1)
return str;// do not replace
char[] ca = str.toCharArray();
char replaceC = '\0';
if (ca[i] == ca[i + 1])
return str;
if (ca[i] == 'a' && ca[i + 1] == 'b') {
replaceC = 'c';
} else if (ca[i] == 'b' && ca[i + 1] == 'c') {
replaceC = 'a';
} else if (ca[i] == 'c' && ca[i + 1] == 'a') {
replaceC = 'b';
}
if (i > 0 && (i + 2) < str.length()) {
return (i > 1) ? str.substring(0, i - 1) + replaceC
+ str.substring(i + 2) : ca[0] + replaceC
+ str.substring(i + 2);
} else if (i == 0 && (i + 2) < str.length()) {
return replaceC + str.substring(i + 2);
} else if (i > 0 && (i + 2) >= str.length()) {
return (i > 1) ? str.substring(0, i - 1) + replaceC : "" + ca[0] + replaceC;
} else if (i == 0 && (i + 2) >= str.length()) {
return replaceC + "";
}
return "";
}
private int min(int a, int b) {
if (a > b)
return b;
else
return a;
}
public int stringReduced(String str, int i) {
if (str.length() == 1)
return 1;
if (this.allEqual(str) > 0 || str.length() == i)
return str.length();
String reduceString = this.replaceTwo(str, i);
int reduceVal = 0;
if (reduceString.equals(str)) {
reduceVal = stringReduced(str, i + 1);
} else {
reduceVal = stringReduced(reduceString, 0);
}
int noreduceVal = stringReduced(str, i + 1);
return min(noreduceVal, reduceVal);
}
}
- mm April 23, 2014