0535. Encode and Decode TinyURL =============================== 题目信息 -------- :题号: 0535 :难度: Medium :主题: 设计、URL 映射、编码解码、对象状态 :原题: `LeetCode 0535 `_ :重点: encode 生成可用于恢复的短链接、decode 必须返回对应原链接、不同链接不能发生不可区分的冲突 题目重述 -------- 设计 ``Codec`` 类,实现 ``encode(longUrl)`` 和 ``decode(shortUrl)``。``encode`` 接收一个长网址并返回它的短网址表示;``decode`` 接收此前生成的短网址并恢复原始长网址。 题目不限定短网址的具体格式或编码方法,但必须保证对每个已编码网址都有 ``decode(encode(longUrl)) = longUrl``。对象可以在多次调用之间保存映射状态;不同长网址生成的可用短网址不能在解码时产生歧义。 自建示例 -------- 编码后能够无损恢复: .. code-block:: text 输入:longUrl = "https://example.com/articles/42" 输出:shortUrl = encode(longUrl),decode(shortUrl) = "https://example.com/articles/42" 解释:短网址文本由实现自行决定,但解码结果必须与原网址完全一致。 两个网址保持独立映射: .. code-block:: text 输入:依次编码 "https://a.example/x" 和 "https://b.example/y" 输出:分别解码两个短网址时返回各自原网址 解释:两个映射不能互相覆盖或混淆。 对象内保存双向映射 ------------------ 题目不要求短网址具有可逆的数学编码,只要求在同一个对象状态中能够恢复。为每个新长网址分配递增编号,生成唯一短网址,并保存短网址到长网址的映射;再次编码同一长网址时复用已有短网址,避免产生不必要的重复键。 C++ 实现 -------- .. code-block:: cpp class Codec { const std::string prefix = "https://tinyurl.com/"; long long nextId = 0; std::unordered_map encoded; std::unordered_map 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)``。