LeetCode 271. 字符串的编码与解码
题目描述
题意分析
将字符串列表编码成一个字符串，并能从编码无损还原原列表。原来的顺序、重复项、空字符串以及每项的具体内容都必须保留。
字符串正文可能含数字或分隔符，因此不能假设某个普通字符永远不会出现在数据里。空列表与只包含一个空字符串的列表也不同。这里的解码入口接收本实现编码函数生成的合法数据。
解法：长度前缀界定每个字符串
核心思路
[!blue]
不靠分隔符划分正文，而为每项添加明确的长度头，格式为“十进制长度、
#、原文”。#只用于确定长度字段在哪里结束；知道长度后，正文就按指定数量读取，不再扫描正文内部的分隔符。解码维护当前位置
index。先逐位累积长度，读到#后跳过它，再截取接下来的length个单位作为一个完整字符串。将指针移动到正文末尾后，那里必定是下一段长度头或整个编码的末尾。每一轮先解析唯一的十进制长度，再按确定边界取正文，因此正文含多少个
#或数字都不会产生歧义。零长度正文也要加入一次空字符串；虽然正文指针不再额外移动，长度头和分隔符已经被消费，循环仍然前进。空列表没有任何片段，编码为空；非空列表即使所有项都是空字符串，也会输出各自的零长度头，因此两者能够区分。Java 的长度与截取都使用 UTF-16 单元，Go 都使用字节，各自的一对编码解码保持单位一致即可往返；这两份实现没有约定一个统一的跨语言字节长度协议。
解题步骤
- 编码时按列表顺序，对每项追加长度、分隔符和原文。
- 解码从字符串开头开始，将分隔符前的数字累积为当前段长度。
- 跳过分隔符，截取恰好该长度的正文并加入结果，包含长度为零的情况。
- 移到正文结束位置，继续解析下一长度头，直到编码全部消费。
- 返回恢复后的列表，保持原顺序与重复项。
代码实现
class Codec {
public String encode(List<String> strs) {
StringBuilder out = new StringBuilder();
for (String s : strs) {
out.append(s.length()).append('#').append(s);
}
return out.toString();
}
public List<String> decode(String s) {
List<String> out = new ArrayList<>();
int index = 0;
while (index < s.length()) {
int length = 0;
while (s.charAt(index) != '#') {
length = length * 10 + s.charAt(index++) - '0';
}
index++;
out.add(s.substring(index, index + length));
index += length;
}
return out;
}
}
import (
"strconv"
"strings"
)
type Codec struct{}
func Constructor() Codec { return Codec{} }
func (c *Codec) Encode(strs []string) string {
var out strings.Builder
for _, s := range strs {
out.WriteString(strconv.Itoa(len(s)))
out.WriteByte('#')
out.WriteString(s)
}
return out.String()
}
func (c *Codec) Decode(s string) []string {
out := []string{}
for index := 0; index < len(s); {
length := 0
for s[index] != '#' {
length = length*10 + int(s[index]-'0')
index++
}
index++
out = append(out, s[index:index+length])
index += length
}
return out
}
复杂度分析
- 时间复杂度：以完整编码长度
L计，编码和解码都为 $O(L)$。长度字段、正文和分隔符都只线性处理，空字符串的段头开销也计入L。- 空间复杂度：$O(L)$，保存编码缓冲或解码结果；解码除返回结果外只需长度与位置等常数状态。
关键点总结
[!green]
- 分隔符只结束长度头，正文边界由长度决定，正文不需要转义。
- 每一项都有自己的头信息，空项、重复项和空列表都能准确还原。
- 编码长度单位必须与解码截取单位一致，不能混用字符数与字节数。
- 当前解码依赖合法编码契约，消费位置始终落在下一段头部。
易错点总结
[!yellow]
- 对整个编码直接按
#切分，正文中的同名字符也会被错误分段。- 长度字段只读一位，无法处理多位长度。
- 长度为零时跳过加入结果，丢失原列表中的空字符串项。
- 没有跳过段头分隔符，或取完正文后没有推进到正确位置，后续片段全部错位。
- 编码记录一种长度单位，解码按另一种单位截取，多字节或多单元字符会破坏边界。
- 直接把合法数据解码器当作任意外部输入的协议校验器，当前代码并不包含格式与越界检查。
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！