Bijective function approach


  • 0
    X

    Use the Bijective function approach. But I think this is not stateless, since I stored the id and long urls?
    reference http://n00tc0d3r.blogspot.com/

    class Solution {
    public:
    
        Solution(){ 
            int i = 0;
            for ( ; i <10; ++i )
            {
                maps1['0'+i] = i;
                maps2[i] = '0'+i;
            }
            for ( i=0; i <26; ++i )
            {
                maps1['a'+i] = i+10;
                maps2[i+10] = 'a'+i;
            }
            for ( i=0; i <26; ++i )
            {
                maps1['A'+i] = i+36;
                maps2[i+36] = 'A'+i;
            }
            nextId = 1;
        }
    
        // Encodes a URL to a shortened URL.
        string encode(string longUrl) {
            string res;
            
            int id = 0;
            if ( mapStr.find( longUrl) != mapStr.end() )
                id = mapStr[longUrl];
            else
            {
                id = nextId++;
                mapStr[longUrl] = id;
                mapInt[id] = longUrl;
            }
            
            while ( id > 0 )
            {
                int digit = id%62;
                res.push_back(maps2[digit]);
                id /=62;
            }
    
            return res;
        }
    
        // Decodes a shortened URL to its original URL.
        string decode(string shortUrl) {
            int id = 0;
            for ( auto letter : shortUrl )
            {
                int digit = maps1[letter];
                id = id*62+digit;
            }
            
            if ( mapInt.find( id) != mapInt.end() )
                return mapInt[id];
            else
                return "";
        }
    protected:
        int nextId;
        unordered_map<char,int> maps1;
        unordered_map<int,char> maps2;
        unordered_map<int,string> mapInt;
        unordered_map<string,int> mapStr;
    };
    

  • 0

    @xiapeggy As you stated, this is not stateless.


  • 0
    J

    I think the encode must include two information, such as, the index and the char in the index of string.


  • 0
    J

    Yes, this is not stateless. This is a system design problem.
    I'm sure in real interview, what they want to hear is …… simply increment identifer method, but not a bijection.


Log in to reply
 

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