C++ sol base62 (no randomness)


  • 0
    M

    Keep two dictionaries: long2short & short2long (always the same size). Use the current size of the dictionary as the index to generate shortUrl (base62).

    eg.
    index 0 -> 0 0 0 0 0 0
    index 1 -> 0 0 0 0 0 1
    index 10 -> 0 0 0 0 0 a
    index 61 -> 0 0 0 0 0 Z
    index 62 -> 0 0 0 0 1 0

    '''
    class Solution {
    public:
    Solution(): prefix("http://tinyurl.com/"),
    candidate("0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"),
    capacity(pow(62, 6)) {}

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if(long2short.find(longUrl) == long2short.end()) {
            size_t index = long2short.size();
            if(index==capacity) throw "OUT OF CAPACITY!!!";
            string shortUrl = index2ShortBase62(index);
            long2short[longUrl] = shortUrl;
            short2long[shortUrl] = longUrl;
        }
        return prefix + long2short[longUrl];
    }
    
    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        try {
            return short2long[shortUrl.substr(19)];
        }
        catch(const string& msg) {
            throw msg;
        }
    }
    

    private:
    const string prefix;
    const string candidate;
    const size_t capacity;
    unordered_map<string, string> long2short, short2long;

    string index2ShortBase62(int num) const {
        string ret;
        while(ret.length()!=6) {
            ret += candidate[num%62];
            num /= 62;
        }
        return ret;
    }
    

    };

    '''


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.