http://sw-engineers.com/wiki/index.php/Cracking_The_Coding_Interview/Q_1.5
Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2blc5a3. If the "compressed" string would not become smaller than the original string, your method should return the original string.
基本上处理字符串的问题都不好用String，主要是出于效率考虑，而且String在递归传值时也不好用。
所以一律用StringBuilder或者StringBuffer。
思路很简单，就是每个字符和它的前一个比较，同时维护一个count变量，记录重复了多少次。
假如不让用StringBuilder，则可以用一个char array来代替StringBuilder
// 不用StringBuilder而用array的方法
public static String compressAlternate(String str) {
int size = countCompression(str);
if(str.length() <= size) {
return str;
}
char[] array = new char[size];
int index = 0;
char last = str.charAt(0);
int count = 1;
for(int i=1; i<str.length(); i++) {
if(str.charAt(i) == last) {
count++;
} else{
index = setChar(array, last, index, count);
last = str.charAt(i);
count = 1;
}
}
index = setChar(array, last, index, count);
return String.valueOf(array);
}
// index:标记当前位置，把字符c和有几个c（count）添加到array数组中
// 最后返回更新过的index
public static int setChar(char[] array, char c, int index, int count) {
array[index] = c;
index++;
char[] cnt = String.valueOf(count).toCharArray();
for(char x : cnt) {
array[index] = x;
index++;
}
return index;
}
Use StringBuilder
public static String compress(String str) {
int finalLength = countCompression(str);
if (finalLength >= str.length()) return str;
StringBuffer compressed = new StringBuffer(finalLength); // initialize capacity
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result.*/
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressed.append(str.charAt(i));
compressed.append(countConsecutive);
countConsecutive = 0;
}
}
return compressed.toString();
}
public static int countCompression(String str) {
int compressedLength = 0;
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result.*/
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressedLength += 1 + String.valueOf(countConsecutive).length();
countConsecutive = 0;
}
}
return compressedLength;
}
public static String compress(String str) {
StringBuilder compressed = new StringBuilder();
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result.*/
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) { //i + 1 >= str.length()
compressed.append(str.charAt(i));
compressed.append(countConsecutive);
countConsecutive = 0;
}
}
return compressed.length() < str.length() ? compressed.toString() : str;
}
Not efficient
public static String compressBad(String str) {
String compressedString = "";
int countConsecutive = 0;
for (int i = 0; i < str.length(); i++) {
countConsecutive++;
/* If next character is different than current, append this char to result.*/
if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
compressedString += "" + str.charAt(i) + countConsecutive;
countConsecutive = 0;
}
}
return compressedString.length() < str.length() ? compressedString : str;
}
