535. Encode and Decode TinyURL

1. Description

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 a class to encode a URL and decode a tiny URL.
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.
Implement the Solution class:

• Solution() Initializes the object of the system.
• String encode(String longUrl) Returns a tiny URL for the given longUrl.
• String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.

2. Example

Example 1

Input: url = “https://leetcode.com/problems/design-tinyurl”
Output: “https://leetcode.com/problems/design-tinyurl”

Explanation:
Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

3. Constraints

• 1 <= url.length <= $10^4$
• url is guranteed to be a valid URL.

4. Solutions

Hash Table

n = longUrl.size()
Encoder
Time complexity: O(n)
Space complexity: O(n)
Decoder
Time complexity: O(1)
Space complexity: O(1)

class Solution {
public:
    string encode(string longUrl) {
        database[id] = longUrl;
        string encode_url = tiny_url_prefix + to_string(id);
        ++id;

        return encode_url;
    }

    string decode(string shortUrl) {
        string sid = shortUrl.substr(tiny_url_prefix.size());
        uint64_t id = stoull(sid);

        return database[id];
    }

private:
    uint64_t id = 0;
    string tiny_url_prefix = string("http://tinyurl.com/");
    unordered_map<uint64_t, string> database;
};