问题描述

编写一个函数，输入一个字符串，返回该字符串的压缩版本。例如，字符串 aaabbbcc 的压缩版本为 a3b3c2。

要求

1. 函数应接受一个字符串作为输入
2. 函数应返回输入字符串的压缩版本
3. 如果压缩后的字符串长度不小于原字符串，则返回原字符串
4. 字符串中只包含大小写字母

示例输入

s = "aaabbbcc"
s = "abc"

示例输出

"a3b3c2"
"abc"

解决思路

1. 遍历字符串：遍历输入的字符串，统计每个字符的出现次数。
2. 压缩字符串：将字符和出现次数拼接成压缩后的字符串。
3. 比较长度：比较压缩后的字符串和原字符串的长度，返回较短的那个。

代码解析

1. 4行开始， 遍历输入的字符串，统计每个字符的出现次数。
2. 第6行： 确保不会超出字符串的长度，并且判断当前字符是否与下一个字符相同。
3. 第9行： 如果与当前字符不同，就将当前字符和出现次数拼接到压缩后的字符串中
4. 第12行： 比较压缩后的字符串和原字符串的长度，返回较短的那个

为了确保压缩的字符串拼接性能，我们采用了StringBuilder来拼接字符串，这样可以避免频繁的字符串拼接操作，提高性能

参考代码

public class Compressor {
    // 压缩字符串, 返回压缩后的字符串
    // Author: ruzhila.cn
    public String compress(String original) {
        StringBuilder compressed = new StringBuilder();
        int countConsecutive = 0;
        for (int i = 0; i < original.length(); i++) {
            countConsecutive++;
            if (i + 1 >= original.length() || original.charAt(i) != original.charAt(i + 1)) {
                compressed.append(original.charAt(i));
                compressed.append(countConsecutive);
                countConsecutive = 0;
            }
        }
        return compressed.length() < original.length() ? compressed.toString() : original;
    }

    public static void main(String[] args) {
        String s = "aaabbbcc";
        StringCompressor compressor = new StringCompressor();
        System.out.println(compressor.compress(s));  // 输出 a3b3c2
    }
}

总结

这段代码实现了对一个字符串进行压缩的算法，代码非常的简洁好理解

这个算法的时间复杂度为O(n)，其中n为字符串的长度。你可以将这段代码集成到你的项目中，用于字符串压缩的功能。

欢迎大家关注 入职啦 (公众号: ruzhila) ，获取更多有趣的编程挑战题和技术干货！

所有的后端面试常见的问题，我们每天都会在我们的编程群里面讨论和Code review, 欢迎大家加入我们的编程群，一起学习和进步。