271. 字符串的编码与解码（中等）

Blind 75 › 271. 字符串的编码与解码（中等） （第 6 章）
文章工具

题目

请设计两个函数：encode 把若干字符串合并成一个字符串；decode 再把这个字符串还原成原来的字符串列表。

难点在于：每个字符串可以是 256 个 ASCII 字符中的任意字符，包括 #、,、数字、空格，甚至空串。因此不能随便选一个“分隔符”直接拼接。

自造示例：["hello","wo#rld",""] 可编码为 "5#hello6#wo#rld0#"，再解码必须得到原来的三个字符串。

约束：1 ≤ strs.length ≤ 200；0 ≤ strs[i].length ≤ 200；字符来自 256 个 ASCII 字符。

思路

一句话：把“找分隔符”换成“先写长度，再写内容”。

最直白的做法是选一个字符当分隔符，例如 ","，编码时 join、解码时 split。如果字符串里永远不会出现逗号，这没问题；但本题字符可以是任意 ASCII 字符，逗号、#、反斜杠都可能出现在内容里，解码时就无法判断它是分隔符还是内容。想用转义（遇到特殊字符就加 ）虽然可行，但编码要扫描、解码要维护转义状态，边界多、容易错。

关键观察：与其让解码器“猜边界”，不如让编码串“自己告诉解码器边界”。在每个字符串前面放 长度#，解码时先读数字直到 #，得到长度，再按这个长度精确切出字符串。这样字符串内容里即使有 # 或数字，也绝不会被误认，因为解码器切完指定长度后，会直接跳到下一个长度字段。

这种“长度 + 分隔 + 内容”的格式自描述、无歧义，而且只需顺序扫描一遍，选它。

解法

两个方向都按同一套规则走：

  1. 编码：对每个 s，依次追加 len(s)、#、s。
  2. 解码：指针 i 从 0 开始；读出 i 到 # 之间的数字作为长度 L；从 # 后一位开始切 L 个字符；指针跳到下一段。
指针 i读到字段长度切出的字符串更新后 i
05#5hello7
76#6wo#rld15
150#0“”17

每个“长度字段 + 内容”都被精确消费，循环结束后解码完成。

下图把上面 2 个步骤串成流程，并逐步演示：

271. 字符串的编码与解码（中等） 解法步骤流程图
图① 解法步骤流程图（共 2 步）。
271. 字符串的编码与解码（中等） 按步骤逐步执行的动画
动图② 按步骤依次推进（循环播放）。

C++

C++ 片段需补全 main() 函数才能运行在实训台打开 →
class Codec {
public:
 // Encodes a list of strings to a single string.
 string encode(vector<string>& strs) {
 string out;
 for (const string& s :
🔒
本篇为付费内容
您已阅读试读部分，购买后即可解锁全文。
⚠️ 本站内容已做唯一性标记并受版权保护，未经授权禁止转载，侵权必究。