LeetCode 535. TinyURL 的加密与解密

2024-07-27 HGNULB 约 11 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 535. TinyURL 的加密与解密

题意分析

设计一个短链服务的两个接口：encode(longUrl) 把任意长网址变成一个形如 http://tinyurl.com/xxxx 的短网址，decode(shortUrl) 把短网址还原成原来的长网址。判题只要求 decode(encode(url)) == url，短码长什么样、有多长、是不是随机，完全由实现者决定。

这是一道设计题而不是算法题，所以要先看清它到底考什么。题目没有给出任何「短码必须能从长链接算出来」的要求，也没有限制内存——这等于明确允许把映射关系存下来。一旦允许存储，decode 就退化成一次查表，全部设计压力都落在 encode 如何生成短码上。

生成短码的核心约束只有一条：不同的长链接必须拿到不同的短码。一旦两个不同的长链接撞到同一个短码，后写入的会覆盖先写入的，decode 必然返回错误结果。这条约束把「用长链接的 hashCode 当短码」这类做法直接判死——哈希值有限而输入无限，冲突不可避免且无法察觉。

另一个隐含要求是同一个长链接反复 encode 应当返回同一个短码。判题不检查这一点，但真实短链服务必须如此，否则每次调用都白白消耗一个新短码。面试中主动做到这点是加分项，代价只是多维护一张反向表。

边界与实现取舍：decode 拿到的是完整短网址，必须先剥掉 http://tinyurl.com/ 前缀才能查表，用「取最后一个 / 之后的部分」比硬编码前缀长度更稳；短码要尽量短，直接用十进制自增数字会很快变长，换成 62 进制能把长度压到十进制的约 $\log_{62}10 \approx 0.56$ 倍；计数器要考虑位宽，用 long 可以覆盖任何现实调用量。

解法：哈希映射短链接

核心思路

先排除两类看似聪明的做法。其一是用长链接的哈希值当短码——String.hashCode() 只有 32 位，输入空间无限，必然存在两个不同网址哈希相同，而这种冲突静默发生、无法自检，是设计题里的硬伤。其二是随机生成短码——每次随机后要循环检测是否已被占用，占用率高时会反复重试，且需要一个高质量随机源，复杂度和确定性都不如自增。

正确的切入点是：短码不需要从长链接推导出来，它只是一个「第几个被登记的链接」的编号。既然如此，用一个单调自增的计数器就能保证「绝不重复」这个唯一硬约束——第 k 次登记拿到编号 k，不同的登记必然拿到不同编号，冲突从根上不存在。

编号直接当短码会太长（第一亿个链接的十进制表示有 9 位）。把它转成 62 进制（0-9 + a-z + A-Z），同样是一亿只需要 5 位字符。62 进制转换本身就是反复除以 62 取余、把余数映射成字符，再把结果反转——因为除法先得到的是最低位。

于是维护两张哈希表和一个计数器：code2url 存「短码 → 长链接」，供 decode 查；url2code 存「长链接 → 短码」，供 encode 判重复用。两张表方向相反，各自服务一个接口的查询方向，这是空间换时间的标准做法。

不变量：任何时刻 code2url 与 url2code 互为逆映射，且两者的大小恒等于已分配的短码个数 id。每次新登记同时往两张表各写一条，这个不变量就一直成立，decode 也就必然能查到 encode 曾返回过的任意短码。

decode 侧只剩一件事：从完整短网址里切出短码。取最后一个 / 之后的子串即可——这个写法不依赖域名前缀的具体长度，换个域名也不用改代码。

解题步骤

在类里放一个 long id = 0 计数器、两张 Map<String, String>、一个 62 个字符的字符表常量。为什么：计数器保证短码唯一，两张表分别服务两个方向的查询，字符表用 static final 声明避免每次调用重新构造。字符表的字符顺序无关紧要，只要固定不变即可。

encode 第一步先查 url2code，命中就直接拼上前缀返回。为什么：同一个长链接不应该消耗第二个短码。这一步必须放在 id++ 之前，否则计数器已经被推进，就算不用也浪费了一个编号。

未命中时先 id++，再用新的 id 生成短码。为什么：从 1 而不是 0 开始编号，可以避开 toBase62(0) 的特殊分支；先自增再取值保证每次调用拿到的编号都不同。

把 (code, longUrl) 写进 code2url，把 (longUrl, code) 写进 url2code，两条一起写。为什么：两张表必须同时更新才能维持互为逆映射的不变量；只写一张会导致要么 decode 查不到、要么重复 encode 判不出。

返回 "http://tinyurl.com/" + code。为什么：题目要求返回的是完整短网址而不是裸短码。

toBase62 里循环执行「取 v % 62 映射成字符、v /= 62」直到 v 为 0，最后把结果反转。为什么：除法先得到的是最低位，所以拼出来的串是倒序的，必须反转才是正确的进制表示。单独处理 x == 0 是因为此时 while 一次都不进，会返回空串。

decode 先用 lastIndexOf('/') 定位分隔符，取其后的子串作为短码。为什么：取最后一个而不是第一个 /，才能跳过 http:// 里的那两个；不硬编码前缀长度，域名改动时代码不用跟着改。

用短码查 code2url 并返回。为什么：decode 的全部工作就是一次哈希查找；查不到时返回空串而不是 null，避免调用方空指针。

走一遍完整的调用序列。初始 id = 0，两张表都空。

调用 encode("https://leetcode.cn/problems/design-tinyurl")：url2code 查不到，id 变成 1，toBase62(1) 里 v = 1，第一轮 r = 1 % 62 = 1 取字符 '1'、v 变 0，循环结束，反转后仍是 "1"。写入 code2url["1"] = 长链接、url2code[长链接] = "1"，返回 "http://tinyurl.com/1"。

再调用 encode("https://example.com")：查不到，id 变成 2，短码为 "2"，两张表各加一条，返回 "http://tinyurl.com/2"。

又调用一次 encode("https://leetcode.cn/problems/design-tinyurl")：这次 url2code 命中，直接返回 "http://tinyurl.com/1"，id 仍是 2，没有浪费编号。

调用 decode("http://tinyurl.com/1")：lastIndexOf('/') 找到下标 18（即 tinyurl.com 后面那个斜杠），截取得到 "1"，查 code2url 得到原始长链接，返回。

顺带看一个进制转换稍长的例子：当 id 涨到 62 时，第一轮 62 % 62 = 0 取 '0'、v = 1；第二轮 1 % 62 = 1 取 '1'、v = 0。拼出的串是 "01"，反转后得 "10"——这正是 62 在 62 进制下的表示。若漏掉反转就会返回 "01"，虽然仍然唯一、不影响判题，但已经不是正确的进制表示，一旦后续需要「从短码反解出编号」就会全盘错乱。

代码实现

import java.util.HashMap;
import java.util.Map;

public class Codec {
    // 自增计数器保证短码绝不重复；用 long 覆盖任何现实调用量。
    private long id = 0;
    private final Map<String, String> code2url = new HashMap<>();
    private final Map<String, String> url2code = new HashMap<>();
    private static final String BASE = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public String encode(String longUrl) {
        // 同一个长链接复用旧短码，判重必须在 id++ 之前。
        String code = url2code.get(longUrl);
        if (code != null) {
            return "http://tinyurl.com/" + code;
        }
        id++;
        code = toBase62(id);
        // 两张表互为逆映射，必须同时写入。
        code2url.put(code, longUrl);
        url2code.put(longUrl, code);
        return "http://tinyurl.com/" + code;
    }

    public String decode(String shortUrl) {
        // 取最后一个 '/' 之后的部分，不依赖前缀的具体长度。
        int idx = shortUrl.lastIndexOf('/');
        String code = idx == -1 ? shortUrl : shortUrl.substring(idx + 1);
        String url = code2url.get(code);
        return url == null ? "" : url;
    }

    private String toBase62(long x) {
        if (x == 0) {
            return "0";
        }
        StringBuilder sb = new StringBuilder();
        long v = x;
        while (v > 0) {
            int r = (int) (v % 62);
            sb.append(BASE.charAt(r));
            v /= 62;
        }
        // 除法先得到低位，拼出来是倒序的，必须反转。
        return sb.reverse().toString();
    }
}

type Codec struct {
	// 自增计数器保证短码绝不重复；uint64 覆盖现实调用量。
	id       uint64
	code2url map[string]string
	url2code map[string]string
}

func Constructor() Codec {
	return Codec{code2url: make(map[string]string), url2code: make(map[string]string)}
}

func (this *Codec) encode(longUrl string) string {
	// 同一个长链接复用旧短码，判重必须在 id++ 之前。
	if code, ok := this.url2code[longUrl]; ok {
		return "http://tinyurl.com/" + code
	}
	this.id++
	code := toBase62(this.id)
	// 两张表互为逆映射，必须同时写入。
	this.code2url[code] = longUrl
	this.url2code[longUrl] = code
	return "http://tinyurl.com/" + code
}

func (this *Codec) decode(shortUrl string) string {
	// 取最后一个 '/' 之后的部分，不依赖前缀的具体长度。
	idx := -1
	for i := len(shortUrl) - 1; i >= 0; i-- {
		if shortUrl[i] == '/' {
			idx = i
			break
		}
	}
	code := shortUrl
	if idx != -1 {
		code = shortUrl[idx+1:]
	}
	return this.code2url[code]
}

func toBase62(x uint64) string {
	base := "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
	if x == 0 {
		return "0"
	}
	buf := make([]byte, 0)
	for x > 0 {
		buf = append(buf, base[x%62])
		x /= 62
	}
	// 除法先得到低位，拼出来是倒序的，必须反转。
	for i, j := 0, len(buf)-1; i < j; i, j = i+1, j-1 {
		buf[i], buf[j] = buf[j], buf[i]
	}
	return string(buf)
}

复杂度分析

时间复杂度：设长链接长度为 $L$、短码长度为 $K=O(\log_{62} id)$。encode 需要哈希长链接并生成短码，时间为 $O(L+K)$；重复编码时只需 $O(L)$。decode 扫描短网址并哈希短码，时间为 $O(K)$（固定域名前缀只贡献常数长度）。

空间复杂度：累计存储为 $O(S+n\log n)$，其中 $S$ 是所有不同长链接的总长度、$n$ 是其数量；两张映射各有 $n$ 个条目，短码总长度为 $O(n\log n)$。

关键点总结

设计题先分清「哪些是题目硬约束、哪些是自己可以定的」。本题唯一的硬约束是短码不重复，认清这点后，自增计数器这个最简单的方案立刻浮出水面。

短码不必从长链接推导。凡是「只要求可还原、不要求可计算」的编码问题，都可以用「登记 + 查表」代替「计算」，从而彻底消灭冲突。

用哈希值当短码是这类题最典型的错误答案。面试时能主动说出「32 位哈希在无限输入空间上必然碰撞，而碰撞会静默产生错误」，比写对代码更能体现设计意识。

需要双向查询就维护双向表。code2url 服务 decode、url2code 服务幂等性，两者同时写入是保持逆映射不变量的关键。

解析短码时取最后一个分隔符，而不是硬编码前缀长度。这个习惯能让代码在域名或路径变化时不受影响。

易错点总结

用 longUrl.hashCode() 当短码：两个不同网址哈希相同 → 后写入的覆盖先写入的，decode 静默返回另一个人的链接，是最严重的设计缺陷。

判重写在 id++ 之后：连续两次 encode 同一个网址 → 第二次虽然返回旧短码，但计数器已白白前进，长期运行会浪费大量编号。

只维护 code2url 一张表：同一个长链接 encode 十次 → 分配十个不同短码、表里存十份重复的长链接，内存线性膨胀。

只维护 url2code 一张表：decode 无从下手 → 只能反向遍历整张表找短码，单次查询退化成 $O(n \cdot L)$。

decode 用 indexOf('/') 而不是 lastIndexOf('/')："http://tinyurl.com/1" → 截出的是 "/tinyurl.com/1"，查表必然落空，返回空串。

decode 用 substring(19) 硬编码前缀长度：一旦短网址前缀改成 "https://tinyurl.com/"（多一个字符）→ 截出的短码首字符被吃掉，全部还原失败。

toBase62 忘记反转：id = 62 → 返回 "01" 而不是 "10"，虽不影响本题判题，但短码不再是合法的进制表示，任何「从短码反解编号」的扩展都会错。

toBase62 漏掉 x == 0 的分支：若计数器从 0 开始编号 → 第一次 while 一次都不进，返回空串，短网址变成 "http://tinyurl.com/"，decode 时截出空串。

62 进制字符表长度不等于 62：例如漏写一个字母只有 61 个字符 → v % 62 取到下标 61 时数组越界抛异常。

decode 查不到时直接返回 code2url.get(code)：短码不存在 → Java 返回 null，调用方拼接或比较时空指针崩溃，应统一降级成空串。

相似题目

题目	难度	考察点
297. 二叉树的序列化与反序列化	困难	同为编解码成对设计，但必须真正把结构写进字符串，不能靠查表作弊
706. 设计哈希映射	简单	要求手写本题直接使用的哈希表本身，考点是散列函数与冲突处理
380. O(1) 时间插入、删除和获取随机元素	中等	同样用两个结构互补，但配的是「哈希表 + 动态数组」以支持随机取值
146. LRU 缓存	中等	在哈希表之外还要维护访问顺序，容量上限带来淘汰逻辑，本题则无需淘汰
208. 实现 Trie (前缀树)	中等	键之间存在前缀共享关系，用树而非平坦映射，换来前缀查询能力
355. 设计推特	中等	多张表之间存在关联与时序，取数据时还要做多路归并，状态复杂度高一档
170. 两数之和 III - 数据结构设计	简单	同为「写入侧与查询侧的取舍」，考的是把开销放在 `add` 还是 `find`
432. 全 O(1) 的数据结构	困难	哈希表需与双向链表联动才能让极值查询也保持常数，是双结构配合的进阶形态