[C++] Using Unordered Maps and a singleton non-random code generator


  • 0

    We assume that the code (the ID tag) is always a string with 6 alphanumeric characters containing 0-9, a-z, A-Z. For instance, "http://tinyurl.com/4e9iAk" is the tiny url for the page "https://leetcode.com/problems/design-tinyurl".

    We also assume that each shortened URL must be unique; that is, no two different URLs can be shortened to the same URL.

    In the following code, CodeGenerator is a singleton class creating next available code (ID tag).

    class CodeGenerator { // a singleton
        const string alphabet = "abcdefghijklmnopqrstuvwxyz0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        int alphabetSize = alphabet.size();
        int indices[6];
        int canGenerate = true;
        CodeGenerator() {} // singleton -> private default constructor
    public:
        static CodeGenerator& getInstance() {
            static CodeGenerator instance;
            return instance;
        }
        std::string nextCode() { // moving indices to make a new available 6-character long code
            if (!canGenerate) return "";
            string code (6, '0');
            for (int i = 0; i < 6; i++) code[i] = alphabet[indices[i]];
            for (int i = 0; i < 6; i++) {
                indices[i] = (indices[i] + 1) % alphabetSize;
                if (indices[i]) break;
                if (i == 5) canGenerate = false;
            }
            return code;
        }
        CodeGenerator(CodeGenerator const&) = delete; // being singleton
        void operator=(CodeGenerator const&) = delete; // being singleton
    };
    
    class Solution {
        const string site = "http://tinyurl.com/"; // length = 19
        unordered_map<string, string> long2code, code2long; // two hash tables
    
    public:
        string encode(string longUrl) {
            auto found = long2code.find(longUrl);
            if (found != long2code.end()) return found->second;
            auto newCode = CodeGenerator::getInstance().nextCode();
            if (!newCode.empty()) {
                long2code.emplace(longUrl, newCode);
                code2long.emplace(newCode, longUrl);
                return site + newCode;
            }
            return "";
        }
        string decode(string shortUrl) {
            auto code = shortUrl.substr(19); // last 6 characters represent the code
            auto found = code2long.find(code);
            return found == code2long.end() ? "" : found->second;
        }
    };
    

Log in to reply
 

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