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:

Theshort key's length shouldequal to 6(without domain and slash). And the acceptable characters are[a-zA-Z0-9]. For example:abcD9E
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/abc
D9E
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/and 6 acceptable characters. For examplehttp://tiny.url/abcD9Eor something else.

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

Solution

class TinyUrl {
private:
    const long long hashSize = 62 ^ 6;
    map<long long, string> id2long;
    const string tinyHeader = "http://tiny.url/";

public:
    /**
     * @param url a long url
     * @return a short url starts with http://tiny.url/
     */
    char number2char(int n) {
        if (n <= 9) {
            return '0' + n;
        } else if (n <= 35) {
            return 'a' + (n - 10);
        } else {
            return 'A' + (n - 36);
        }
    }

    long long char2number(char c) {
        if ('0' <= c && c <= '9') {
            return c - '0';
        } else if ('a' <= c && c <= 'z') {
            return c - 'a' + 10;
        } else if ('A' <= c && c <= 'Z') {
            return c - 'A' + 36;
        }
    }

    long long shortURL2id(string url) {
        long long id = 0;
        for(int i = 0; i < url.size(); i++) {
            id = id * 62 + char2number(url[i]);
        }
        return id;
    }

    string longToShort(string& url) {
        long long number = 0;
        for(int i = 0; i < url.size(); i++) {
            number = (number * 256 + (long long)url[i]) % hashSize;
        }

        // solve conflict
        while (id2long.count(number) > 0 && id2long[number] != url) {
            number++;
        }
        id2long[number] = url;

        string shortURL = "";
        while (number > 0) {
            int mod = number % 62;
            number /= 62;
            shortURL = number2char(mod) + shortURL;
        }

        while (shortURL.size() < 6) {
            shortURL = "0" + shortURL;
        }

        shortURL = tinyHeader + shortURL;

        return shortURL;
    }

    /**
     * @param url a short url starts with http://tiny.url/
     * @return a long url
     */
    string shortToLong(string& url) {
        int id = shortURL2id(url.substr(tinyHeader.size(), url.size()));
        if (id2long.count(id) > 0) {
            return id2long[id];
        }

        return "";
    }
};

其他解:

http://www.vikasing.com/2010/11/simple-url-shortening-algorithm-in-java.html