深入解析 Python 字符串压缩与解压缩算法（devops-exercises 实战题解）

导读

本文以 devops-exercises 仓库中的 Python 算法练习 compress_string_solution.md 为核心，完整拆解「行程长度编码（Run-Length Encoding，RLE）」的压缩与解压缩双向实现。通过逐行剖析源码、推演运行轨迹、分析边界条件与时空复杂度，读者不仅能直接掌握 'aaaabbccc' -> 'a4b2c3' 这类高频面试题的解题套路，还能理解其背后的指针扫描思想，并将其迁移到日志压缩、DNA 序列编码等真实场景。

一、题目背景：行程长度编码是什么

压缩字符串是算法面试中的经典送分题，其本质是行程长度编码（RLE）：把连续相同字符的「行程（run）」压缩成「字符 + 出现次数」的形式。本题出自仓库的 compress_string.md，共两问：

1. 编写一个函数，对给定字符串进行压缩
   • 'aaaabbccc' → 'a4b2c3'
   • 'abbbc' → 'a1b3c1'
2. 编写一个函数，对给定字符串进行解压缩
   • 'a4b2c3' → 'aaaabbccc'
   • 'a1b3c1' → 'abbbc'

注意示例中的一个重要细节：单次出现的字符也会被标记为 1（如 'a1'），因此该编码是「字符 + 频次」成对出现的定长二元组格式，这为解压缩算法提供了极大的简化空间（见第四节）。

二、压缩函数逐行拆解

完整实现位于 compress_string_solution.md，核心代码如下：

def compress_str(mystr: str) -> str:

	result = ''

	if mystr:
		prevchar = mystr[0]
	else:
		return result

	count = 1
	for nextchar in mystr[1:]:
		if nextchar == prevchar:
			count += 1
		else:
			result += prevchar + str(count)
			count = 1
			prevchar = nextchar

	result += prevchar + str(count)
	return result

2.1 空字符串防护

函数第一处关键分支是 if mystr: 空串检查。当输入为空字符串时，直接返回初始化的空 result，避免后续 mystr[0] 抛出 IndexError。这是典型的防御式编程，也是面试中容易被追问的边界条件。

2.2 指针扫描的核心思想

算法使用双指针思想（此处以 prevchar 与 nextchar 隐式体现）：

• prevchar 记录当前正在统计的行程字符；
• count 记录该字符连续出现的次数；
• 通过 for nextchar in mystr[1:] 从第二个字符开始遍历，与 prevchar 逐一比对。

行程切换逻辑：当 nextchar == prevchar 时，只做 count += 1，继续累加；一旦遇到不同字符，就把 prevchar + str(count) 追加到 result，然后将 count 重置为 1、prevchar 更新为新字符，开始统计下一个行程。

收尾逻辑：循环结束后，最后一个行程尚未写入结果（因为触发写入的条件是「遇到下一个不同字符」，而末尾没有下一个字符），因此循环外必须补一行 result += prevchar + str(count)。忘记这一步是本题最常见的 bug，会让输出丢失最后一段行程。

2.3 运行轨迹推演

以 'aaaabbccc' 为例逐步追踪：

步骤	prevchar	遍历字符	count	result
初始化	'a'	—	1	''
1	'a'	'a'	2	''
2	'a'	'a'	3	''
3	'a'	'a'	4	''
4	'a'	'b'	1（写入 'a4'）	'a4'
5	'b'	'b'	2	'a4'
6	'b'	'c'	1（写入 'b2'）	'a4b2'
7	'c'	'c'	2	'a4b2'
收尾	—	—	写入 'c2'	'a4b2c3'

最终输出 'a4b2c3'，与题目预期完全一致。

2.4 复杂度分析

• 时间复杂度：O(n)，单次线性遍历，n 为字符串长度；
• 空间复杂度：O(n)，result 在最坏情况下（所有字符都不相同，如 'abcdef' → 'a1b1c1d1e1f1'）长度约为输入的 2 倍。

一个值得注意的反直觉结论：当字符串没有重复字符时，RLE 压缩后反而变大（每个字符都要附带数字 1）。这说明 RLE 只对存在大量连续重复的输入有效，理解这一点有助于在真实场景中判断是否适合采用该算法。

三、压缩函数的易错点与可运行性说明

• 数字与字符拼接：result += prevchar + str(count) 中必须用 str(count) 显式把整数转成字符串，否则会触发 TypeError（字符串与整数无法直接拼接）。
• 函数可直接复制运行：该函数无任何外部依赖，使用标准 Python 即可执行：

python3 -c "
def compress_str(mystr):
    result = ''
    if mystr:
        prevchar = mystr[0]
    else:
        return result
    count = 1
    for nextchar in mystr[1:]:
        if nextchar == prevchar:
            count += 1
        else:
            result += prevchar + str(count)
            count = 1
            prevchar = nextchar
    result += prevchar + str(count)
    return result

print(compress_str('aaaabbccc'))  # a4b2c3
print(compress_str('abbbc'))      # a1b3c1
print(compress_str(''))           # 空串
"

四、解压缩函数逐行拆解

def decompress_str(mystr: str) -> str:
	result = ''
	for index in range(0, len(mystr), 2):
		result += mystr[index] * int(mystr[index + 1])
	return result

4.1 步长为 2 的成对遍历

由于压缩格式约定「字符 + 频次」成对出现，解压缩可以大大简化：用 range(0, len(mystr), 2) 以步长 2 遍历，每次取偶数位字符 mystr[index] 与其后一位的数字 mystr[index + 1]。

4.2 字符串乘法运算符

核心技巧是 Python 的字符串乘法：'a' * 4 得到 'aaaa'。int(mystr[index + 1]) 把数字字符转成整数作为乘数，结果追加到 result。以 'a4b2c3' 为例：

• index=0：'a' * 4 → 'aaaa'
• index=2：'b' * 2 → 'bb'
• index=4：'c' * 3 → 'ccc'

拼接得到 'aaaabbccc'，正确还原。

4.3 前提约束与复杂度

• 前提：该实现要求输入严格满足「字符 + 一位数字」的交替格式。若某段行程次数超过 9（如 'a10' 中的 '10' 是两位），步长 2 的遍历会错位解析，解出的结果是错误的。这是题目示例格式（单字符 + 单数字）下的简化解，理解其适用边界比背代码更重要。
• 时间复杂度：O(n + L)，其中 n 为压缩串长度、L 为还原后的总长度；
• 空间复杂度：O(L)，结果字符串长度即原始数据长度。

五、仓库内的配套练习与延伸阅读

字符串处理是 topics/python 目录下的系列练习之一，可与其他题目对照学习，巩固字符串与数据类型基础：

• reverse_string.md 及其参考答案：对比 my_string[::-1] 切片技巧与逐字符拼接的循环实现，后者注释明确指出性能极慢（每次拼接都创建新字符串），与本文压缩函数的 O(n) 线性拼接形成对比，是理解 Python 字符串不可变性的好素材；
• data_types.md 与参考答案：巩固 list / str / int / float / bool 等基础数据类型认知，压缩函数中 str(count) 的类型转换正是此类知识的直接应用；
• sort_solution.md：在不使用 sorted() / .sort() 的前提下实现降序排序，与本题同样强调不依赖内置函数、手写核心逻辑的训练思路；
• advanced_data_types.md：进阶数据类型的识别练习，可用于检验对集合、字典、元组等类型的掌握。

此外，仓库根目录的 coding/python 下还提供了可直接运行的算法实现，例如 binary_search.py（二分查找，O(log n)）与 merge_sort.py（归并排序，O(n log n)），它们与本文的压缩算法共同构成了一套覆盖线性扫描、分治、双指针等经典范式的最小算法题库，适合作为面试前的快速刷题清单。

六、扩展思考：从面试题到工程实践

掌握基础实现后，可以进一步思考以下升级方向（仓库原题未涉及，属于能力迁移）：

1. 支持多位数字：压缩时对超过 9 的行程写入多位数字，解压时改用正则或状态机解析数字部分，打破「成对步长 2」的限制；
2. 无重复字符时不膨胀：在压缩函数中判断，若压缩后长度不小于原长度则返回原串，这是许多真实压缩库（如 RLE 的 GIF/PCX 变体）采用的策略；
3. 处理空串与非法输入：解压函数同样需要空串保护，并对「数字缺失」「数字为 0」等非法格式做健壮性校验。

小结

本文以 devops-exercises 仓库的 compress_string_solution.md 为骨架，完整覆盖了题目要求、双指针扫描的压缩实现、成对遍历的解压实现、边界条件、复杂度分析与运行验证。其核心要点可归纳为：压缩靠「指针扫描 + 行程计数」，收尾补写最后一段行程；解压靠「成对遍历 + 字符串乘法」，但需理解步长 2 的格式前提。掌握这一题，等于同时拿下了 RLE 编码原理、Python 字符串操作与面试边界条件考察三个知识点。