Given a long url, make it shorter. To make it simpler, let's ignore the domain name.

You should implement two methods:

• longToShort(url) . Convert a long url to a short url.
• shortToLong(url) . Convert a short url to a long url starts with http://tiny.url/ .

You can design any shorten algorithm, the judge only cares about two things:

1. The short key 's length should equal to 6 (without domain and slash). And the acceptable characters are [a-zA-Z0-9] . For example: abcD9E
2. No two long urls mapping to the same short url and no two short urls mapping to the same long url.

Have you met this question in a real interview?

Yes

Example

Given url =http://www.lintcode.com/faq/?id=10, run the following code (or something similar):

short_url = longToShort(url) // may return http://tiny.url/abcD9E
long_url = shortToLong(short_url) // return http://www.lintcode.com/faq/?id=10

The short_url you return should be unique short url and start withhttp://tiny.url/and6acceptable characters. For example "http://tiny.url/abcD9E" or something else.

The long_url should behttp://www.lintcode.com/faq/?id=10in this case.

const string TINYURL = "http://tiny.url/";
typedef unsigned long long uint_64t;

class TinyUrl {
public:
    /**
     * @param url a long url
     * @return a short url starts with http://tiny.url/
     */
    string longToShort(string& url) {
        // Write your code here
        uint_64t id = 0;

        for (auto ch : url) {
            id = (id * 256ULL + ch) % MAX_ID;
        }
        while (mp.find(id) != mp.end() && mp[id] != url) {
            ++id;
        }
        mp[id] = url;

        string shortKey = idToShortKey(id);
        return TINYURL + shortKey;
    }

    /**
     * @param url a short url starts with http://tiny.url/
     * @return a long url
     */
    string shortToLong(string& url) {
        // Write your code here
        string shortKey = getShortKey(url);
        uint_64t id = shortKeyToID(shortKey);
        return mp[id];
    }

private:


    map<uint_64t, string> mp;


    static const uint_64t MAX_ID = 56800235584ULL;

    string getShortKey(string& url) {
        return url.substr(TINYURL.size(), url.size() - TINYURL.size());
    }

    string idToShortKey(uint_64t id) {
        string shortKey;
        char c[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

        while (id > 0) {
            shortKey += c[id % 62];
            id = id / 62;
        }

        while(shortKey.size() < 6) {
            shortKey += 'a';
        }

        std:reverse(shortKey.begin(), shortKey.end());
        return shortKey;
    }

    uint_64t shortKeyToID(string& shortKey) {
        uint_64t id = 0;
        for (auto ch : shortKey) {
            if (ch >= 'a' && ch <= 'z') {
                id = id * 62 + ch - 'a';
            }
            if (ch >= 'A' && ch <= 'Z') {
                id = id * 62 + ch - 'A' + 26;
            }
            if (ch >= '0' && ch <= '9') {
                id = id * 62 + ch - '0' + 52;
            }
        }
        return id;
    }

};