[535. encryption and decryption of tinyurl]

source ： Power button （LeetCode）

describe ：

TinyURL It's a kind of URL Simplify services , such as ： When you enter a URL https://leetcode.com/problems/design-tinyurl when , It will return a simplified URL http://tinyurl.com/4e9iAk . Please design a class to encrypt and decrypt TinyURL .

There is no limit to how encryption and decryption algorithms are designed and operated , You just need to guarantee one URL Can be encrypted into a TinyURL , And this TinyURL It can be restored to the original by decryption URL .

Realization Solution class ：

• Solution() initialization TinyURL System object .
• String encode(String longUrl) return longUrl Corresponding TinyURL .
• String decode(String shortUrl) return shortUrl The original URL . The subject data guarantees a given shortUrl Is encrypted by the same system object .

Example ：

 Input ：url = "https://leetcode.com/problems/design-tinyurl"
 Output ："https://leetcode.com/problems/design-tinyurl"

 explain ： 
Solution obj = new Solution();
string tiny = obj.encode(url); //  Returns the result of encryption  TinyURL .
string ans = obj.decode(tiny); //  Returns the original after decryption  URL .

Tips ：

• 1 <= url.length <= 10⁴
• Topic data assurance url Is an effective URL

Preface

The title does not require the same URL Must be encrypted to the same TinyURL, Therefore, the method in this paper does not meet the same URL Encrypt to the same TinyURL. If you want to achieve the same URL Encrypt to the same TinyURL, Save an additional from URL To TinyURL Mapping .

Method 1 ： Self increasing
Encode function

Use self increasing id As longUrl Key , Every time I receive one longUrl All will id Add one , Set the key value to (id,longUrl) Insert database dataBase, Then return with \textit{id}id As a string of shorUrl.

Decode function

take shortUrl Convert to corresponding }key, Then in the database dataBase Search for key Corresponding longUrl.

Code ：

class Solution {
    
private:
    unordered_map<int, string> dataBase;
    int id;

public:
    Solution() {
    
        id = 0;
    }

    string encode(string longUrl) {
    
        id++;
        dataBase[id] = longUrl;
        return string("http://tinyurl.com/") + to_string(id);
    }

    string decode(string shortUrl) {
    
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};

Execution time ：4 ms, In all C++ Defeated in submission 70.90% Users of
Memory consumption ：6.8 MB, In all C++ Defeated in submission 36.81% Users of
Complexity analysis
Time complexity ：
Encode function ： O(n), among n Is string longUrl The length of .
Decode function ： O(1). We should shortUrl Treat as a finite length string .
Spatial complexity ：
Encode function ： O(n). Save string longUrl need O(n) Space .
Decode function ： O(1).

Method 2 ： Hash generation

Code ：

const long long k1 = 1117;
const long long k2 = 1e9 + 7;

class Solution {
    
private:
    unordered_map<int, string> dataBase;
    unordered_map<string, int> urlToKey;

public:
    Solution() {
    

    }

    string encode(string longUrl) {
    
        if (urlToKey.count(longUrl) > 0) {
    
            return string("http://tinyurl.com/") + to_string(urlToKey[longUrl]);
        }
        long long key = 0, base = 1;
        for (auto c : longUrl) {
    
            key = (key + c * base) % k2;
            base = (base * k1) % k2;
        }
        while (dataBase.count(key) > 0) {
    
            key = (key + 1) % k2;
        }
        dataBase[key] = longUrl;
        urlToKey[longUrl] = key;
        return string("http://tinyurl.com/") + to_string(key);
    }

    string decode(string shortUrl) {
    
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};

Execution time ：0 ms, In all C++ Defeated in submission 100.00% Users of
Memory consumption ：7 MB, In all C++ Defeated in submission 10.69% Users of

Method 3 ： Random generation

Code ：

class Solution {
    
private:
    unordered_map<int, string> dataBase;

public:
    Solution() {
    
        srand(time(0));
    }

    string encode(string longUrl) {
    
        int key;
        while (true) {
    
            key = rand();
            if (dataBase.count(key) == 0) {
    
                break;
            }
        }
        dataBase[key] = longUrl;
        return string("http://tinyurl.com/") + to_string(key);
    }

    string decode(string shortUrl) {
    
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};

Execution time ：4 ms, In all C++ Defeated in submission 70.90% Users of
Memory consumption ：6.8 MB, In all C++ Defeated in submission 31.09% Users of

author：LeetCode-Solution