题目

TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.

要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。

思路

给每个URL生成一个随机唯一的字符串，用两个哈希表，其中一个哈希表存储long url和short url的对应关系，另一个哈希表存储short url和long url的对应关系。

C++代码

#include <iostream>
#include <vector>
#include <map>
#include <set>
using namespace std;
class Solution {
public:
    vector<int> words;
    Solution() {
        for (char c = 'a'; c <= 'z'; c++) words.push_back(c);
        for (char c = 'A'; c <= 'Z'; c++) words.push_back(c);
        for (char c = '0'; c <= '9'; c++) words.push_back(c);
    }
    string baseURL = "http://tinyurl.com/";
    map<string, string> longToShorts, shortToLongs;
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        return getShortURLElseCreate(longUrl);
    }
    
    string getShortURLElseCreate(string longUrl) {
        string shortURL = "";
        if (longToShorts.count(longUrl)) shortURL = longToShorts[longUrl];
        else {
            do {
                shortURL = baseURL;
                for (int i = 0; i < 8; ++i) {
                    shortURL.push_back(words[rand() % words.size()]);
                }
            } while (shortToLongs.count(shortURL));
            longToShorts[longUrl] = shortURL;
            shortToLongs[shortURL] = longUrl;
        }
        return shortURL;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return shortToLongs[shortUrl];
    }
};
int main(int argc, const char * argv[]) {
    Solution solution;
    string url = "https://www.baidu.com";
    string longUrl, shortUrl;
    shortUrl = solution.encode(url);
    cout << shortUrl << endl;
    cout << solution.decode(shortUrl) << endl;
    return 0;
}

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/encode-and-decode-tinyurl