第24章：字符串的压缩：如 'aaabb' -> 'a3b2'

字符串压缩，说白了就是「把重复的字符数出来」。

比如 "aaabb" 变成 "a3b2"，看起来很简单对吧？

但我在实际项目中踩过不少坑。今天咱们就把它彻底讲透。

24.1 什么是字符串压缩？

字符串压缩的核心思想是：用「字符 + 出现次数」来替代连续重复的字符。

举个例子：

• "aaa" → "a3"
• "aabbb" → "a2b3"
• "abc" → "a1b1c1"（但通常我们只压缩长度超过1的）

你可能会问：这有什么用？

我当年在做一个嵌入式日志系统时，需要把大量重复的传感器数据压缩后传输。那时候带宽只有9600bps，不压缩根本传不完。字符串压缩算法帮了大忙。

24.2 基础实现：逐字符扫描

最直接的方法就是：遍历字符串，数出每个连续段的长度。

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

char* compressString(const char* str) {
    int len = strlen(str);
    if (len == 0) return NULL;

    // 压缩后的字符串最长不会超过原串的2倍（最坏情况每个字符都不同）
    char* result = (char*)malloc(len * 2 + 1);
    if (!result) return NULL;

    int idx = 0;
    int i = 0;

    while (i < len) {
        char current = str[i];
        int count = 1;

        // 统计连续相同字符的个数
        while (i + count < len && str[i + count] == current) {
            count++;
        }

        // 写入字符和次数
        result[idx++] = current;
        idx += sprintf(result + idx, "%d", count);

        // 跳过已处理的字符
        i += count;
    }

    result[idx] = '\0';
    return result;
}

int main() {
    char test[] = "aaabb";
    char* compressed = compressString(test);
    printf("原串: %s\n", test);
    printf("压缩: %s\n", compressed);
    free(compressed);
    return 0;
}

这段代码的核心逻辑就两件事：数数，然后写进去。

我个人习惯把 sprintf 用在拼接数字上，因为它比手动转字符串更安全。

24.3 进阶：原地压缩（In-place）

如果题目要求你不能用额外空间，怎么办？

比如 LeetCode 443 题「压缩字符串」，要求原地修改字符数组。

思路是这样的：

• 用两个指针：read 负责读，write 负责写
• 读指针扫描原串，写指针在数组前面覆盖写入

int compress(char* chars, int charsSize) {
    int write = 0;
    int read = 0;

    while (read < charsSize) {
        char current = chars[read];
        int count = 0;

        // 统计连续相同字符
        while (read < charsSize && chars[read] == current) {
            read++;
            count++;
        }

        // 写入字符
        chars[write++] = current;

        // 如果次数大于1，写入数字
        if (count > 1) {
            char numStr[12];
            int numLen = sprintf(numStr, "%d", count);
            for (int i = 0; i < numLen; i++) {
                chars[write++] = numStr[i];
            }
        }
    }

    return write;  // 返回新长度
}

这里有个细节：次数为1时不写数字。这是很多题目的默认规则。

我曾经在面试时忘了这个条件，结果把 "abc" 压缩成了 "a1b1c1"，面试官当场就笑了。

24.4 避坑指南：我踩过的三个坑

做字符串压缩，看起来简单，但坑不少。我一个个说。

坑1：数字位数问题

如果某个字符连续出现了100次，你要写 "a100"，而不是 "a100" 写成 "a100" 没问题，但如果你用 itoa 或者手动转，很容易漏掉位数。

我建议直接用 sprintf，它自动处理多位数。

坑2：内存分配大小

压缩后的字符串可能比原串长吗？

会的！比如 "abc" 每个字符都不同，如果次数为1也写数字，结果变成 "a1b1c1"，长度翻倍。

所以分配内存时，最坏情况是 len * 2 + 1。

坑3：空字符串和单字符

空串直接返回空。单字符如 "a"，压缩后还是 "a"（次数1不写）。

我见过有人把 "a" 压缩成 "a1"，这在某些场景下是错的。

24.5 扩展：解压缩

有压缩就得有解压缩。解压缩其实更简单：

char* decompressString(const char* compressed) {
    int len = strlen(compressed);
    // 最坏情况：每个字符只出现1次，解压后长度翻倍
    char* result = (char*)malloc(len * 2 + 1);
    if (!result) return NULL;

    int idx = 0;
    int i = 0;

    while (i < len) {
        char current = compressed[i];
        i++;

        // 读取数字
        int count = 0;
        while (i < len && compressed[i] >= '0' && compressed[i] <= '9') {
            count = count * 10 + (compressed[i] - '0');
            i++;
        }

        // 如果没读到数字，说明次数为1
        if (count == 0) count = 1;

        // 重复写入字符
        for (int j = 0; j < count; j++) {
            result[idx++] = current;
        }
    }

    result[idx] = '\0';
    return result;
}

这里要注意：数字可能是多位数。比如 "a12" 表示12个a，不是1个a和2个什么。

我当年写解压缩时，忘了处理多位数，结果 "a12" 解出了 "a" + "1" + "2"，调试了半天才发现。

24.6 性能分析

操作	时间复杂度	空间复杂度
压缩（非原地）	O(n)	O(n)
压缩（原地）	O(n)	O(1)
解压缩	O(n)	O(n)

都是线性时间，效率很高。

24.7 知识结构图

下面这张图帮你理清本章的核心逻辑：

24.8 实际项目中的应用

字符串压缩不只是面试题。我在实际项目中用过好几次：

• 日志压缩：嵌入式设备日志中大量重复的 "OK"、"ERROR"，压缩后存储空间节省60%
• 网络传输：传感器数据流中连续相同的数值，压缩后带宽占用降低
• 配置文件：某些配置项有大量重复的默认值，压缩后文件更小

但要注意：不是所有场景都适合。如果数据本身随机性很强，压缩后反而更大。我建议先做个小测试，看看压缩率再决定是否使用。

24.9 总结

字符串压缩的核心就三点：

1. 扫描：找到连续重复的字符段
2. 计数：统计出现次数
3. 写入：字符 + 次数（次数为1时不写）

代码实现不难，但细节决定成败。多位数处理、内存分配、原地覆盖，这些都是容易出问题的地方。

我建议你自己动手写一遍，然后试试 "aaaaaaaaaa"（10个a）和 "ababab" 这种边界情况。跑通了，才算真正掌握。

---

公众号：蓝海资料掘金营，微信 deep3321