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;
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容