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)。
解法二:哈希生成,选两个合适的质数k1_11=1117,k2_22=109^99+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)。