问题描述：
TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.
Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.
解题思路：
这道题看到要将长的转换成短的，我能想到hashmap，但是对碰撞问题我是没有什么好的解决方案。
看了Grandyang的分析。
这里使用了rand()函数来随机生成并从字典里获取字符。
生成完了6位字符串后，需要检查是否发生碰撞，若发生碰撞则重新生成。
用了两个hashmap来存储：
short2long：主要用于转换
long2short：主要用于查重
代码：
class Solution {public: ???Solution(){ ???????dict = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"; ???????short2long.clear(); ???????long2short.clear(); ???????srand(time(NULL)); ???} ???????// Encodes a URL to a shortened URL. ???string encode(string longUrl) { ???????if(long2short.count(longUrl)) ???????????return "http://tinyurl.com/" + long2short[longUrl]; ???????string randStr; ???????for(int i = 0; i < 6; i++){ ???????????randStr.push_back(dict[rand() % 62]); ???????} ???????????????int idx = 0; ???????while(short2long.count(randStr)){ ???????????idx %= 6; ???????????randStr[idx] = dict[rand() % 62]; ???????} ???????short2long[randStr] = longUrl; ???????long2short[longUrl] = randStr; ???????return "http://tinyurl.com/" + randStr; ???} ???// Decodes a shortened URL to its original URL. ???string decode(string shortUrl) { ???????string randStr = shortUrl.substr(shortUrl.find_last_of("/")+1); ???????return short2long.count(randStr) ? short2long[randStr] : shortUrl; ???}private: ???unordered_map<string, string> short2long, long2short; ???string dict;};// Your Solution object will be instantiated and called as such:// Solution solution;// solution.decode(solution.encode(url));535. Encode and Decode TinyURL
原文地址：https://www.cnblogs.com/yaoyudadudu/p/9186784.html