Tiny Url

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 withhttp://tiny.url/.

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

1. Theshort key's length shouldequal 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.

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.

S1: hashmap, incremental index.

用两个hashmap存储short和long的关系，这里生成的url数受限于int的最大值。若不想受限于int，可在每一位上随机生成index。

class TinyUrl {
public:
    /**
     * @param url a long url
     * @return a short url starts with http://tiny.url/
     */
    string longToShort(string& url) {
        if (url2id.find(url) == url2id.end()) {
            url2id[url] = curId;
            id2url[curId] = url;
            curId++;
        }
        return "http://tiny.url/" + idToShortUrl(url2id[url]);
    }

    /**
     * @param url a short url starts with http://tiny.url/
     * @return a long url
     */
    string shortToLong(string& url) {
        int id = shortUrlToId(url.substr(16, 6));
        if (id2url.find(id) == id2url.end()) {
            return "";
        }
        return id2url[id];
    }

private:
    int curId = 0;
    unordered_map<string, int> url2id;
    unordered_map<int, string> id2url;
    string idToShortUrl(int id) {
        string chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        string shortUrl = "";
        while (id > 0) {
            shortUrl += chars[id%62];
            id /= 62;
        }
        while (shortUrl.size() < 6) {
            shortUrl = '0' + shortUrl;
        }
        return shortUrl;
    }
    int shortUrlToId(string url) {
        int id = 0;
        for (int i = 0; i < 6; ++i) {
            id = id * 62 + to62base(url[i]);
        }
        return id;
    }
    int to62base(const char a) {
        if (a <= '9' && a >= '0') return a - '0';
        if (a <= 'z' && a >= 'a') return a - 'a' + 10;
        return a - 'A' + 36;
    }
};