1.6 String Compression

Implement a method to perform basic string compression using the counts of repeated characters. For example, the string aabcccccaaa would become a2b1c5a3. If the “compressed” string would not become smaller than the original string, your method should return the original string. You can assume the string has only uppercase and lowercase letters (a - z).

Hint

• Do the easy thing first. Compress the string, then compare the lengths.
• Be careful that you aren’t repeatedly concatenating strings together. This can be very inefficient.

Solution

本题需要我们压缩给定的字符串，用数字表示前面一个字母的重复次数，这种方法对于重复字母较少的字符串，压缩后反而会出现长度变大的情况，因此需要先对压缩后的长度进行计算，如果压缩后长度变小才开始执行压缩。注意当开始压缩时，避免直接使用字符串的相加，当数据量较大时这种运算非常低效。

public String stringCompress(String str) {
	if (str == null || str.isEmpty()) return str;
	int newLength = calculateLength(str);
	if (newLength >= str.length()) return str;

	StringBuilder sb = new StringBuilder(newLength);
	int count = 0;
	for (int i = 0; i < str.length(); i++) {
		count++;
		if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
			sb.append(str.charAt(i));
			sb.append(count);
			count = 0;
		}
	}
	return sb.toString();
}

private int calculateLength(String str) {
	int result = 0, count = 0;
	for (int i = 0; i < str.length(); i++) {
		count++;
		if (i + 1 >= str.length() || str.charAt(i) != str.charAt(i + 1)) {
			result += 1 + String.valueOf(count).length();
			count = 0;
		}
	}
	return result;
}