LeetCode 面试题 01.06. 字符串压缩

约 4 分钟
文章信息 12 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 10-20 程序员面试金典（第 6 版） 腾讯 字节 阿里 美团 京东 虾皮
标签
字符串 双指针

题目描述

✅ 面试题 01.06. 字符串压缩

image-20260928223639188

题意分析

输入只含大小写英文字母，大小写按不同字符处理。把每一段连续相同字符写成“字符 + 次数”，出现一次也要写次数，分散出现的相同字符不能合并。

只有完整编码严格短于原串时才返回编码，否则返回原串。因此，先按连续段构造候选结果，再判断它是否真的缩短了字符串。

解法：连续段计数模拟

核心思路

[!blue]

left 指向当前段的第一个字符，right 从 left + 1 开始，遇到相同字符就继续前进。停止时，right 要么指向第一个不同字符，要么等于字符串长度，因此 [left, right) 正好是一个完整连续段，长度为 right - left。

将该段的字符和段长的完整十进制表示追加到缓冲区，再令 left = right。字符变化时，新段从刚才遇到的不同字符开始，不会漏掉它；到达末尾时，最后一段也已完成写入，不需要额外收尾。

候选长度只会增加。每写完一段，如果长度已经不小于原串，后续再追加内容也不可能变短，可以立即返回原串。只有一直保持更短并处理完全部连续段，才返回压缩结果。

解题步骤

  1. 初始化 left = 0 和结果缓冲区。
  2. 从 left + 1 开始移动 right，直到越界或字符变化。
  3. 追加 S[left] 与段长 right - left。Java 用 StringBuilder.append(int)，Go 用 strconv.AppendInt 写入完整数字，而不是将次数转成一个字符。
  4. 若当前结果长度已不小于原串，直接返回原串；否则令 left = right。
  5. 所有段处理完后返回压缩串。

空串不会进入循环，直接得到空串。题目只含英文字母，因此 Java 按 char、Go 按字节比较都能正确识别字符。

代码实现

class Solution {
    public String compressString(String S) {
        int n = S.length();
        StringBuilder compressed = new StringBuilder();

        for (int left = 0; left < n; ) {
            int right = left + 1;

            while (right < n && S.charAt(right) == S.charAt(left)) {
                right++;
            }

            compressed.append(S.charAt(left)).append(right - left);

            // 候选长度只会增长，一旦不再更短便可直接返回原串。
            if (compressed.length() >= n) {
                return S;
            }

            left = right;
        }

        return compressed.toString();
    }
}

import "strconv"

func compressString(S string) string {
    compressed := make([]byte, 0, len(S))

    for left := 0; left < len(S); {
        right := left + 1
        for right < len(S) && S[right] == S[left] {
            right++
        }
        compressed = append(compressed, S[left])
        compressed = strconv.AppendInt(compressed, int64(right-left), 10)
        // 候选长度只会增长，一旦不再更短便可直接返回原串。
        if len(compressed) >= len(S) {
            return S
        }
        left = right
    }
    return string(compressed)
}

复杂度分析

  • 时间复杂度：$O(n)$。各连续段互不重叠，扫描总量为 $O(n)$；每段计数的十进制位数不超过该段长度，写入结果的总量也是 $O(n)$。
  • 空间复杂度：$O(n)$。最坏情况下结果缓冲区与原串同阶；提前判定不改变渐进复杂度。

关键点总结

[!green]

  • 统计的是连续段，不是字符在整串中的总频次。
  • [left, right) 精确表示当前段，段长直接是 right - left，无需单独处理最后一段。
  • 只有压缩串严格更短时才能返回；等长也返回原串。

易错点总结

[!yellow]

  • 统计整串字符频次会把非相邻的相同字符合并，丢失原有段的顺序。
  • 只在候选长度大于原串时返回原串，会错误地采用等长编码；判断条件应为 >=。
  • 将次数强转成字符只能得到一个字符，无法表示完整的多位十进制计数。
  • 段结束后没有令 left = right，会重复扫描或陷入死循环。

相似题目

题目 难度 关联与区别
443. 压缩字符串 中等 原题只在次数大于1时写计数且原地压缩，本题每段都形成字符加次数，候选不更短就返回原串。
38. 外观数列 中等 同样按连续段读出字符与次数，本题只压缩一次，原题反复描述前一轮结果。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/35734145
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！