LeetCode 补充题 105. 定长数字字符串的可逆编码
题目描述
给你一个恰好包含
60位数字的十进制字符串s，其中可能包含前导零。请实现可逆的编码和解码：将
s编码为恰好34个可复制的 ASCII 字符，并能从编码结果完整还原原字符串，包括前导零。编码结果使用不带填充符的 Base64url 字符集。协议双方已约定原字符串长度为
60，无需支持其他长度或任意文本。解码时需要拒绝非法编码。
示例 1：
输入：
s = "0" 重复 60 次
输出：编码为 "A" 重复 34 次；解码后为原来的 60 个 "0"
解释： 数值 0 用 25 个零字节表示，Base64url 不带填充后为 34 个 A。
提示：
- 输入仅含
0…9，固定长度60。 - 协议双方约定该长度；这不是对任意文本或未知长度数据的通用压缩。
- 非法编码须拒绝。
题意分析
原串有
10^60种可能，保存其数值需要向上取整log₂(10^60)，即 200 位，也就是 25 字节。固定长度协议让前导零数量能够从解码后的十进制长度恢复，无需逐个保存数字字符。Base64url 将二进制数据转换为可复制的字符。25 字节在去掉填充符后恰好是 34 个字符；直接对原来的 60 个文本字节做 Base64 编码反而会变长。
解法：固定宽度大整数与 Base64url
核心思路
[!blue]
编码先验证原串恰好由 60 位十进制数字组成，再转成非负大整数，以无符号大端形式写入固定 25 字节。Java 的
toByteArray()可能带前置符号字节，因此从尾部复制有效字节；不足的高位保持为 0。解码先检查字符长度和 Base64url 格式，再要求恰好得到 25 字节。将解码结果重新编码并与原编码比较，可以拒绝非规范尾部位或其他等价但不符合协议的表示。
25 字节还可表示大于等于
10^60的数，所以必须继续检查解码数值的十进制长度不超过 60。最后在左侧补零到 60 位。数值与固定宽度都恢复后，原字符串便能被唯一还原。
解题步骤
- 验证输入恰有 60 位十进制数字。
- 按无符号大端写入固定 25 字节，再做无填充 Base64url 编码。
- 解码验证长度、规范形式和范围，再补足 60 位十进制宽度。
代码实现
class Solution {
public String encode(String s) {
if (s.length() != 60 || !s.matches("[0-9]{60}")) {
throw new IllegalArgumentException("expected 60 decimal digits");
}
byte[] raw = new BigInteger(s).toByteArray();
byte[] fixed = new byte[25];
int count = Math.min(raw.length, 25);
System.arraycopy(raw, raw.length - count, fixed, 25 - count, count);
return Base64.getUrlEncoder().withoutPadding().encodeToString(fixed);
}
public String decode(String code) {
if (code.length() != 34) {
throw new IllegalArgumentException("invalid length");
}
byte[] raw = Base64.getUrlDecoder().decode(code);
if (raw.length != 25
|| !Base64.getUrlEncoder().withoutPadding().encodeToString(raw).equals(code)) {
throw new IllegalArgumentException("noncanonical encoding");
}
String s = new BigInteger(1, raw).toString();
if (s.length() > 60) {
throw new IllegalArgumentException("out of range");
}
return "0".repeat(60 - s.length()) + s;
}
}
import (
"encoding/base64"
"fmt"
"math/big"
"strings"
)
func encode(s string) (string, error) {
if len(s) != 60 {
return "", fmt.Errorf("expected 60 decimal digits")
}
for _, c := range s {
if c < '0' || c > '9' {
return "", fmt.Errorf("invalid digit")
}
}
n, ok := new(big.Int).SetString(s, 10)
if !ok {
return "", fmt.Errorf("invalid integer")
}
fixed := make([]byte, 25)
n.FillBytes(fixed)
return base64.RawURLEncoding.EncodeToString(fixed), nil
}
func decode(code string) (string, error) {
if len(code) != 34 {
return "", fmt.Errorf("invalid length")
}
raw, err := base64.RawURLEncoding.Strict().DecodeString(code)
if err != nil {
return "", err
}
if len(raw) != 25 || base64.RawURLEncoding.EncodeToString(raw) != code {
return "", fmt.Errorf("noncanonical encoding")
}
s := new(big.Int).SetBytes(raw).String()
if len(s) > 60 {
return "", fmt.Errorf("out of range")
}
return strings.Repeat("0", 60-len(s)) + s, nil
}
复杂度分析
- 时间复杂度：$O(1)$，题目固定为 60 位数字和 25 字节，各步骤都有固定上界。
- 空间复杂度：$O(1)$，大整数、字节缓冲区及结果长度均固定。
若推广到任意长度，需重新计算大整数进制转换成本，不能继续沿用常数复杂度。
关键点总结
[!green]
数值编码压缩的是数字串的取值空间；固定长度约定用于恢复前导零，不能仅对原 ASCII 文本做 Base64。
易错点总结
[!yellow]
必须保留固定宽度约定才能还原前导零；直接对 60 个 ASCII 字节做 Base64 会变长，不会缩短。