Formatted question description: https://leetcode.ca/all/535.html

535. Encode and Decode TinyURL

Level

Medium

Description

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Solution

Use a map to store each encoded short URL and the corresponding long URL before encoding. Maintain a counter count that represents the number of URLs that have been encoded, which is initially 0.

Each time encode is called, increase count by 1, and create the short URL as "http://tinyurl.com/" + count. Map the short URL to the original long URL, and the key-value pair (the key is the short URL and the value is the long URL) is stored in the map.

Each time decode is called, simply obtain the long URL from the map using the short URL as the key.

  • 
    public class Encode_and_Decode_TinyURL {
        class Codec {
            private static final String BASE_HOST = "http://tinyurl.com/";
            private static final String SEED = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    
            // maintain 2 mapping relationships, could be in memory or database or disk file
            private Map<String, String> keyToUrl = new HashMap<>();
            private Map<String, String> urlToKey = new HashMap<>();
    
            // Encodes a URL to a shortened URL.
            public String encode(String longUrl) {
                if (urlToKey.containsKey(longUrl)) { // could also be collision and hash to different tinyUrl
                    return BASE_HOST + urlToKey.get(longUrl);
                }
    
                String key = null;
                do {
                    StringBuilder sb = new StringBuilder();
                    for (int i = 0; i < 6; i++) {
                        int r = (int)(Math.random() * SEED.length());
                        sb.append(SEED.charAt(r));
                    }
                    key = sb.toString();
                } while (keyToUrl.containsKey(key));
    
                keyToUrl.put(key, longUrl);
                urlToKey.put(longUrl, key);
                return BASE_HOST + key;
            }
    
            // Decodes a shortened URL to its original URL.
            public String decode(String shortUrl) {
                return keyToUrl.get(shortUrl.replace(BASE_HOST, ""));
            }
        }
    
    }
    
  • Todo
    
  • class Codec:
        
        BASE = 62
        UPPERCASE_OFFSET = 55
        LOWERCASE_OFFSET = 61
        DIGIT_OFFSET = 48
        num_sender = 0
        url = {}
    
        def encode(self, longUrl):
            """Encodes a URL to a shortened URL.
            
            :type longUrl: str
            :rtype: str
            """
            
            if Codec.num_sender == 0:
                Codec.url[Codec.num_sender] = longUrl
                return '0'
            s_url = ''
            while Codec.num_sender > 0:
                tail = Codec.num_sender % Codec.BASE
                s_url = self.parse_chr(tail) + s_url
                Codec.num_sender //= Codec.BASE
            
            Codec.url[Codec.num_sender] = longUrl
            Codec.num_sender += 1
            return s_url
            
        def decode(self, shortUrl):
            """Decodes a shortened URL to its original URL.
            
            :type shortUrl: str
            :rtype: str
            """
            num = 0
            for i, char in enumerate(reversed(shortUrl)):
                num += self.parse_ord(char) * (Codec.BASE**i)
            return Codec.url[num]
        
        def parse_ord(self, char):
            if char.isdigit():
                return ord(char) - Codec.DIGIT_OFFSET
            elif char.islower():
                return ord(char) - Codec.LOWERCASE_OFFSET
            elif char.isupper():
                return ord(char) - Codec.UPPERCASE_OFFSET
            else:
                raise ValueError('%s is not a valid character' % char)
                
        def parse_chr(self, integer):
            if integer < 10:
                return chr(integer + DIGIT_OFFSET)
            elif 10 <= integer <= 35:
                return chr(integer + UPPERCASE_OFFSET)
            elif 36 <= integer < 62:
                return chr(integer + LOWERCASE_OFFSET)
            else:
                raise ValueError('%d is not a valid integer in the range of base %d' % (integer, Codec.BASE))
    
    # Trie
    class Codec:
        BASE = 62
        num_sender = 0
        ALNUM = string.ascii_letters + '0123456789'
        d_map = {c: i for i, c in enumerate(ALNUM)}
        url = {}
    
        def encode(self, longUrl):
            pk = Codec.num_sender
            s_url = ''
            while pk > 0:
                pk, tail = divmod(pk, Codec.BASE)
                s_url = Codec.ALNUM[tail] + s_url
    
            Codec.url[pk] = longUrl
            Codec.num_sender += 1
            if pk == 0:
                s_url = Codec.ALNUM[0]
            return s_url 
    
        def decode(self, shortUrl):
            pk = sum(Codec.d_map[c]*Codec.BASE**i 
                     for i, c in enumerate(reversed(shortUrl)))
            return Codec.url[pk]
    
    

All Problems

All Solutions