0535. Encode and Decode TinyURL¶
题目信息¶
- 题号:
0535
- 难度:
Medium
- 主题:
设计、URL 映射、编码解码、对象状态
- 原题:
- 重点:
encode 生成可用于恢复的短链接、decode 必须返回对应原链接、不同链接不能发生不可区分的冲突
题目重述¶
设计 Codec 类,实现 encode(longUrl) 和 decode(shortUrl)。encode 接收一个长网址并返回它的短网址表示;decode 接收此前生成的短网址并恢复原始长网址。
题目不限定短网址的具体格式或编码方法,但必须保证对每个已编码网址都有 decode(encode(longUrl)) = longUrl。对象可以在多次调用之间保存映射状态;不同长网址生成的可用短网址不能在解码时产生歧义。
自建示例¶
编码后能够无损恢复:
输入:longUrl = "https://example.com/articles/42"
输出:shortUrl = encode(longUrl),decode(shortUrl) = "https://example.com/articles/42"
解释:短网址文本由实现自行决定,但解码结果必须与原网址完全一致。
两个网址保持独立映射:
输入:依次编码 "https://a.example/x" 和 "https://b.example/y"
输出:分别解码两个短网址时返回各自原网址
解释:两个映射不能互相覆盖或混淆。
对象内保存双向映射¶
题目不要求短网址具有可逆的数学编码,只要求在同一个对象状态中能够恢复。为每个新长网址分配递增编号,生成唯一短网址,并保存短网址到长网址的映射;再次编码同一长网址时复用已有短网址,避免产生不必要的重复键。
C++ 实现¶
class Codec {
const std::string prefix = "https://tinyurl.com/";
long long nextId = 0;
std::unordered_map<std::string, std::string> encoded;
std::unordered_map<std::string, std::string> original;
public:
std::string encode(std::string longUrl) {
auto existing = original.find(longUrl);
if (existing != original.end()) return existing->second;
std::string shortUrl = prefix + std::to_string(nextId++);
original[longUrl] = shortUrl;
encoded[shortUrl] = longUrl;
return shortUrl;
}
std::string decode(std::string shortUrl) {
auto it = encoded.find(shortUrl);
return it == encoded.end() ? "" : it->second;
}
};
代码分析¶
递增编号保证同一对象生成的短键不冲突,反向表保证 decode(encode(url)) 返回原文本;双向表让重复编码可复用而不影响正确性。单次操作平均时间复杂度为 O(1)``(不计字符串哈希长度),空间复杂度为已编码网址总量 ``O(q)。