doocs/leetcode 题解精讲：面试题 01.06 字符串压缩（双指针 Run-Length 编码）

• 示例工程
• 教程

导读

本文基于 doocs/leetcode 仓库中 lcci/01.06.Compress String/README.md 的官方题解，深入讲解《程序员面试金典（第 6 版）》面试题 01.06「字符串压缩」的完整解题思路与多语言实现。这是一道经典的游程编码（Run-Length Encoding, RLE）入门题：利用字符重复出现的次数实现基本压缩，且仅当压缩结果更短时才返回压缩串。读完本文，你将掌握双指针分段计数的核心思想、边界条件（何时保留原串）的处理技巧，以及该题在 Python、Java、C++、Go、Rust、JavaScript、Swift 7 种语言下的可运行参考实现，并能直接对照仓库源码进行练习与验证。

题目背景与核心概念

问题描述

字符串压缩。利用字符重复出现的次数，编写一种方法，实现基本的字符串压缩功能。例如，字符串aabcccccaaa会变为a2b1c5a3。若"压缩"后的字符串没有变短，则返回原先的字符串。可以假设字符串中只包含大小写英文字母（a 至 z）。

这正是游程编码（RLE）的经典定义：把一段连续出现的相同字符，替换为「字符 + 连续出现次数」的形式。

示例分析

示例 1（压缩生效）：

输入："aabcccccaaa" 输出："a2b1c5a3"

逐段拆解：

• aa→a2
• b→b1
• ccccc→c5
• aaa→a3

拼接得到a2b1c5a3，长度为 8，短于原串长度 11，故返回压缩串。

示例 2（压缩失效）：

输入："abbccd" 输出："abbccd" 解释："abbccd"压缩后为"a1b2c2d1"，比原字符串长度更长。

abbccd压缩后为a1b2c2d1，长度 8 反而大于原串长度 6，因此必须返回原字符串。这个示例点明了本题最关键的分支逻辑：压缩不是无条件进行的，只有压缩结果严格更短时才采用。

约束条件

• 字符串长度在 [0, 50000] 范围内，即可能为空串，也可能长达 5 万字符；
• 字符串只包含大小写英文字母（a - z），共 52 种可能字符。

长度上限 50000 意味着时间复杂度必须控制在 $O(n)$ 级别，暴力嵌套循环在最坏情况下会退化到 $O(n^2)$，属于不可接受的实现。

解法：双指针（一次扫描完成分段）

思路推导

压缩串由「字符 + 连续出现次数」拼接而成，且仅当短于原串时才采用。最直观的想法是对每个位置向右数相同字符的个数，但这样虽然最坏情况仍是线性，指针却会反复回退，实现不清晰、易出错。

核心洞察是：同一段连续字符只需报告一次，问题本质是找出每一段连续字符的左右端点。

因此可以采用双指针：

1. 用指针i标记当前连续段的起始位置；
2. 用指针j从i + 1开始向右扫描，直到遇到第一个与S[i]不同的字符；
3. 此时j - i就是该段连续字符的长度，把S[i]与长度拼接进结果串t；
4. 将i直接移动到j（跳过整段），继续下一轮。

扫描过程中每个字符恰好被访问一次，与「双指针找连续段」完全同构。事实上 Python 的groupby正是按相等关系分段的封装，其生成的段与显式双指针完全一致——groupby（或显式双指针）按相等关系分段，将字符与段长写入t，最后按长度取S与t中较短者。

算法流程

输入：字符串 S，长度 n 初始化：结果串 t 为空 i = 0 while i < n: j = i + 1 while j < n 且 S[j] == S[i]: j += 1 t 追加 (S[i], j - i) # 字符 + 连续出现次数 i = j if len(t) < n: 返回 t else: 返回 S

复杂度分析

• 时间复杂度：$O(n)$。指针i、j均只向前移动，每个字符恰好被扫描一次；
• 空间复杂度：$O(n)$。结果串t在最坏情况下长度与原串同数量级（如每个字符都不同时，t长度约为 $2n$，此时会返回原串，但构建t仍需线性空间）。

其中 $n$ 为字符串长度。

多语言实现（仓库源码对照）

以下实现均直接取自仓库lcci/01.06.Compress String/目录下的官方Solution.*源码文件，与 README 文档中的示例代码一一对应。

Python3（groupby 一行解法）

文件：Solution.py

class Solution: def compressString(self, S: str) -> str: t = "".join(a + str(len(list(b))) for a, b in groupby(S)) return min(S, t, key=len)

要点解读：

• groupby(S)按相邻相等关系将字符串分段，每段产出(字符, 迭代器)；
• len(list(b))把迭代器转为列表求长度，即连续出现次数；
• min(S, t, key=len)直接按长度取较短者，优雅地实现了「压缩串不更短则返回原串」的分支。

Java

文件：Solution.java

class Solution { public String compressString(String S) { int n = S.length(); StringBuilder sb = new StringBuilder(); for (int i = 0; i < n;) { int j = i + 1; while (j < n && S.charAt(j) == S.charAt(i)) { ++j; } sb.append(S.charAt(i)).append(j - i); i = j; } String t = sb.toString(); return t.length() < n ? t : S; } }

要点解读：

• 使用StringBuilder而非字符串拼接，避免频繁创建不可变 String 对象，是 Java 高效字符串构建的推荐做法；
• while内层循环用j探测连续段右边界，j - i即段长；
• 最后以t.length() < n判断是否采用压缩串。

C++

文件：Solution.cpp

class Solution { public: string compressString(string S) { int n = S.size(); string t; for (int i = 0; i < n;) { int j = i + 1; while (j < n && S[j] == S[i]) { ++j; } t += S[i]; t += to_string(j - i); i = j; } return t.size() < n ? t : S; } };

要点解读：

• 借助std::string的+=运算符追加字符，to_string(j - i)将整数段长转为字符串；
• 比较t.size()与n决定返回压缩串还是原串。

Go

文件：Solution.go

func compressString(S string) string { n := len(S) sb := strings.Builder{} for i := 0; i < n; { j := i + 1 for j < n && S[j] == S[i] { j++ } sb.WriteByte(S[i]) sb.WriteString(strconv.Itoa(j - i)) i = j } if t := sb.String(); len(t) < n { return t } return S }

要点解读：

• strings.Builder是 Go 中高效构建字符串的标准工具；
• WriteByte写入字符，strconv.Itoa将整数段长转为字符串后WriteString写入；
• Go 中len()返回字节数，由于本题限定 a-z 大小写英文字母（单字节 ASCII），len(t)与字符数一致，比较正确。

Rust

文件：Solution.rs

impl Solution { pub fn compress_string(s: String) -> String { let mut cs: Vec<char> = s.chars().collect(); let mut t = Vec::new(); let mut i = 0; let n = s.len(); while i < n { let mut j = i + 1; while j < n && cs[j] == cs[i] { j += 1; } t.push(cs[i]); t.extend((j - i).to_string().chars()); i = j; } let t = t.into_iter().collect::<String>(); if s.len() <= t.len() { s } else { t } } }

要点解读：

• 先将字符串转为Vec<char>以便按下标访问，规避 Rust 字符串 UTF-8 字节索引的复杂性；
• 用Vec<char>暂存字符，extend((j - i).to_string().chars())展开数字字符；
• 注意这里的返回条件为s.len() <= t.len()时返回原串（与"短于"等价，且对空串同样安全）。

JavaScript

文件：Solution.js

/** * @param {string} S * @return {string} */ var compressString = function (S) { const n = S.length; const t = []; for (let i = 0; i < n;) { let j = i + 1; while (j < n && S.charAt(j) === S.charAt(i)) { ++j; } t.push(S.charAt(i), j - i); i = j; } return t.length < n ? t.join('') : S; };

要点解读：

• 用数组t收集字符与数字，最后t.join('')拼接为字符串；
• 巧妙之处：比较长度时使用t.length（数组元素个数），等价于最终拼接串的长度，避免提前拼接带来的额外开销；
• S.charAt(j)与S.charAt(i)使用全等===比较。

Swift

文件：Solution.swift

class Solution { func compressString(_ S: String) -> String { let n = S.count var compressed = "" var i = 0 while i < n { var j = i let currentChar = S[S.index(S.startIndex, offsetBy: i)] while j < n && S[S.index(S.startIndex, offsetBy: j)] == currentChar { j += 1 } compressed += "\(currentChar)\(j - i)" i = j } return compressed.count < n ? compressed : S } }

要点解读：

• Swift 的String不支持整数下标直接索引，需通过S.index(S.startIndex, offsetBy: i)构造索引；
• 字符串插值"\(currentChar)\(j - i)"完成字符与段长的拼接；
• compressed.count统计字符个数（非字节数），与原串字符数n比较。

边界情况与常见易错点

1. 空串输入：n = 0时循环不执行，t为空串，len(t) < n为假，直接返回原串（空串）。所有实现对此均安全。
2. 单字符输入：如"a"，压缩结果为"a1"（长度 2 > 1），应返回原串"a"。任何把单字符也压缩的实现都会出错。
3. 全相同字符：如"aaaa"→"a4"（长度 2 < 4），压缩生效，这是最理想的压缩场景。
4. 全不同字符：如"abcdef"→"a1b1c1d1e1f1"（长度 12 > 6），必须返回原串，此时压缩反而膨胀。
5. 长度比较的方向：只有压缩串严格更短（t.length < n）才返回t；相等时应返回原串。Rust 实现写成s.len() <= t.len() ? s : t是等价的安全写法。
6. 计数为 1 也要输出：b1、d1这类长度为 1 的段不能省略计数，这是 RLE 的固定格式，也是导致"压缩后变长"的根本原因。

变体与延伸思考

本题是游程编码（RLE）最基础的应用，其双指针分段思想可以平滑迁移到一系列相邻分组问题：

• 统计连续段：如找出字符串中所有连续相同字符段的起止位置与长度，思路与本题完全一致；
• 图像/二进制游程压缩：RLE 广泛用于 BMP 等位图格式与简单报文压缩，本题是其字符版最小模型；
• 滑动窗口类问题：本题指针单调前移、绝不回退的特性，与滑动窗口"右指针扩展、左指针收缩"的模式同源，是理解双指针技巧的良好起点。

在 doocs/leetcode 仓库中，本题位于lcci/（程序员面试金典）目录下，同一目录还收录了大量同级别的字符串、链表、栈与图论面试题，读者可通过 lcci/README.md 总览全部题解，对照不同语言实现进行系统训练。

总结

面试题 01.06「字符串压缩」是一道短小精悍的 RLE 实现题，考察点集中在三点：能否识别"按连续段分组"这一核心结构、能否用双指针一次扫描完成分组、以及能否正确处理"压缩后未变短则返回原串"的分支。doocs/leetcode 仓库提供了 README.md 的完整思路推导，以及 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.rs、Solution.js、Solution.swift 七种语言的官方实现，时间复杂度均为 $O(n)$、空间复杂度 $O(n)$。建议读者先独立手写双指针版本，再对照各语言源码体会语言特性（如 Python 的groupby、Go 的strings.Builder、Rust 的Vec<char>索引技巧）对同一算法的表达差异。

• 示例工程
• 教程