LeetCode 535. TinyURL 的加密与解密

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 <= 104
题目数据保证 url 是一个有效的 URL

解法一：可将长url存入数据库中，id为自增主键，每次存放后会得到数据库中一个自增长的id，然后将带有该id的url作为短url：

class Solution {
public:Solution () {id = 0;}// Encodes a URL to a shortened URL.string encode(string longUrl) {db[id] = longUrl;string shortUrl = string("http://tinyurl.com/") + to_string(id);++id;return shortUrl;}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx = shortUrl.rfind('/') + 1;int id = stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:int id;unordered_map<int, string> db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

如果长url的长度为n，此算法中，encode方法的时间复杂度为O（n），空间复杂度为O（n）；decode方法的时间复杂度为O（1），空间复杂度为O（1）。

解法二：哈希生成，选两个合适的质数k${}_1$=1117，k${}_2$=10${}^9$+7，使用以下方法计算长url的哈希值：

然后encode函数将哈希值和长url存入数据库，并返回含有哈希值的短url。decode函数可根据短url中的哈希值从数据库中取出长url。

当发生哈希冲突时，采用线性探测再散列的方法，将key加1，直到没有冲突。相同的长url的哈希值相同，哈希冲突可能会频繁发生，为避免这一点，我们使用一个额外的哈希表记录从长url到哈希值的映射。

const long long k1 = 1117;
const long long k2 = 1e9 + 7;class Solution {
public:// Encodes a URL to a shortened URL.string encode(string longUrl) {if (urlToKey[longUrl] > 0) {return string("http://tinyurl.com/") + to_string(urlToKey[longUrl]);}int key = 0, base = 1;for (char c : longUrl) {int key = (key + c * base) % k2;int base = (base * k1) % k2;}while (db.find(key) != db.end()) {key = (key + 1) % k2;}db[key] = longUrl;return string("http://tinyurl.com/") + to_string(key);}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx = shortUrl.rfind('/') + 1;int id = stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:unordered_map<int, string> db;unordered_map<string, int> urlToKey;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

如果长url的长度为n，此算法中，encode方法的时间复杂度为O（n），在数据量远小于10e9+7的情况下，哈希冲突很少发生，空间复杂度为O（n）；decode方法的时间复杂度为O（1），空间复杂度为O（1）。

计算字符串的哈希时，类似于计算一个数字，如1234，它等于1 * 10³ + 2 * 10² + 3 * 10 + 4 * 1。

解法三：随机生成，随机生成一个key，如果key已存在，则继续生成，直到出现不存在的key：

class Solution {
public:// Encodes a URL to a shortened URL.string encode(string longUrl) {default_random_engine e(time(0));uniform_int_distribution<int> u(0, INT_MAX);int key = u(e);while (db.find(key) != db.end()) {key = u(e);}db[key] = longUrl;return string("http://tinyurl.com/") + to_string(key);}// Decodes a shortened URL to its original URL.string decode(string shortUrl) {int idStartIdx = shortUrl.rfind('/') + 1;int id = stoi(shortUrl.substr(idStartIdx, shortUrl.size() - idStartIdx));return db[id];}private:unordered_map<int, string> db;
};// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

如果长url的长度为n，此算法中，encode方法的时间复杂度为O（n），空间复杂度为O（n）；decode方法的时间复杂度为O（1），空间复杂度为O（1）。