共计 3474 个字符，预计需要花费 9 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 535. TinyURL 的加密与解密 ，难度为 中等。
Tag :「哈希表」、「模仿」
TinyURL 是一种 URL 简化服务，比方：当你输出一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的 URL http://tinyurl.com/4e9iAk。
请你设计一个类来加密与解密 TinyURL。
加密和解密算法如何设计和运作是没有限度的，你只须要保障一个 URL 能够被加密成一个 TinyURL，并且这个 TinyURL 能够用解密办法复原成本来的 URL。
实现 Solution 类：
Solution()初始化TinyURL零碎对象。String encode(String longUrl)返回longUrl对应的TinyURL。String decode(String shortUrl)返回shortUrl本来的URL。题目数据保障给定的shortUrl是由同一个零碎对象加密的。
示例：
输出：url = "https://leetcode.com/problems/design-tinyurl"
输入："https://leetcode.com/problems/design-tinyurl"
解释：Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后失去的 TinyURL。string ans = obj.decode(tiny); // 返回解密后失去的本来的 URL。提醒：
- $1 <= url.length <= 10^4$
- 题目数据保障
url是一个无效的URL
模仿 + 哈希表
对于每个 longUrl 咱们都在「大写字母 / 小写字母 / 数字」中随机 $k = 6$ 位作为其映射标识，这须要应用一个哈希表 tiny2Origin 进行记录。
同时了避免雷同的 longUrl 屡次调用，确保 encode 服务的「幂等性」，咱们再额定建设哈希表 origin2Tiny 来记录原串和映射标识的对应关系。
Java 代码：
public class Codec {Map<String, String> origin2Tiny = new HashMap<>(), tiny2Origin = new HashMap<>();
String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
String prefix = "https://acoier.com/tags/";
int k = 6;
Random random = new Random();
public String encode(String longUrl) {while (!origin2Tiny.containsKey(longUrl)) {char[] cs = new char[k];
for (int i = 0; i < k; i++) cs[i] = str.charAt(random.nextInt(str.length()));
String cur = prefix + String.valueOf(cs);
if (tiny2Origin.containsKey(cur)) continue;
tiny2Origin.put(cur, longUrl);
origin2Tiny.put(longUrl, cur);
}
return origin2Tiny.get(longUrl);
}
public String decode(String shortUrl) {return tiny2Origin.get(shortUrl);
}
}Python 代码：
class Codec:
def __init__(self):
self.origin_to_tiny = {}
self.tiny_to_origin = {}
self.k = 6
self.prefix = 'https://acoier.com/tags/'
self.ss = string.ascii_letters + string.digits
def encode(self, longUrl: str) -> str:
while longUrl not in self.origin_to_tiny.keys():
cur = ''.join([self.ss[random.randint(0,len(self.ss) - 1)] for _ in range(self.k)])
if cur in self.tiny_to_origin.keys():
continue
self.tiny_to_origin[cur] = longUrl
self.origin_to_tiny[longUrl] = cur
return self.origin_to_tiny[longUrl]
def decode(self, shortUrl: str) -> str:
return self.tiny_to_origin[shortUrl]- 工夫复杂度：
encode操作复杂度为 $O(C + L)$，其中 $C = 6$ 为短串长度，$L$ 为传入参数longUrl的长度（存入哈希表须要计算longUrl哈希值，该过程须要遍历longUrl）；decode操作复杂度为 $O(C)$，其中 $L$ 为传入参数shortUrl的长度，该长度固定为prefix长度加 $6$ - 空间复杂度：$O(K \times L)$，其中 $K$ 为调用次数，$L$ 为均匀
longUrl长度
对于应用「自增 id」的答疑
群里有同学问到为啥要应用「哈希存储映射关系」的形式，而不是用「自增 id」的形式，感觉可能是一部分同学的独特纳闷，这里对立答复一下。
其中两点较为致命的弊病是：
-
应用「自增
id」更容易被枚举；（再补充，提出原问题的好奇宝宝又问了另外一个问题）对于被枚举的害处：粗略来说会导致安全性降落，被攻打的可能性大大加强。因为可枚举意味着，不能光靠 URL 特定发放来确保安全。
联合具体场景来说，假如某个流动日期生成了短 URL 的流动链接，只有特定用户能够拜访，可枚举意味着竞品只须要大略晓得你自增 id 以后在什么范畴即可拿到流动链接，即便流动链接做了鉴权，也能通过攻打伎俩导致服务申请数量突增，影响实在的流动用户应用。
或者这个场景并不致命，竞品要拿到流动链接有很多形式，未必是通过枚举短 URL 来做到。
但另外一个场景则是致命的，就是可枚举会导致应用短 URL 服务的「验证服务」生效。
例如某个服务会通过「邮件 / 短信」发送短 URL 链接，让用户通过点击短 URL 来验证是否为某个「邮箱 / 手机号」的拥有者，短 URL 可枚举，意味着只须要晓得以后自增
id大略范畴，就可通过枚举的形式拜访到实在的验证地址，从而实现「不收到某个邮件 / 短信」也能够通过验证的目标。 - 相比于应用「哈希存储映射关系」的形式，不好重用：
举个🌰，例如映射关系都是 $7$ 天过期，每天会产生了 $10$ 个短 URL，当进行到第 $8$ 天，此时 `id` 曾经自增到 $71$，同时第一天产生的短 URL 已过期，然而实现上，咱们不好将 `id` 进行回拨（须要思考当重用数字用完后要回到 $71$ 的地位）。也就是说，发现而且重用某些数字段（过期的 `id`）会为“自增”带来困扰，而引入「重用池」则违反了抉择自增计划的初衷。但「哈希存储映射关系」要实现重用则是简略的，如果随机产生的短 URL 发生冲突，只须要间接回绝进行重试即可，一旦产生短 URL 无抵触，则能够间接应用。同时因为随机通常遵从某种散布，咱们毋庸引入「过期工夫戳」等信息，即可达到「某个短 URL 在应用后的一段时间后，都不会被随机到（不会在过期后就被迅速重用）」的作用，这一点能够通过调大 $k$ 值来进一步保障。防杠申明：当然，如果你只是在单纯的做算法题，就当我没说 🤣
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.535 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSource/LogicStack-LeetCode。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
