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, ""));
        }
    }

}

############

public class Codec {
    private Map<String, String> m = new HashMap<>();
    private int idx = 0;
    private String domain = "https://tinyurl.com/";

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        String v = String.valueOf(++idx);
        m.put(v, longUrl);
        return domain + v;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        int i = shortUrl.lastIndexOf('/') + 1;
        return m.get(shortUrl.substring(i));
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

class Codec:
    def __init__(self):
        self.m = defaultdict()
        self.idx = 0
        self.domain = 'https://tinyurl.com/'

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL."""
        self.idx += 1
        self.m[str(self.idx)] = longUrl
        return f'{self.domain}{self.idx}'

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL."""
        idx = shortUrl.split('/')[-1]
        return self.m[idx]


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))

############

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]

class Solution {
public:
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        string v = to_string(++idx);
        m[v] = longUrl;
        return domain + v;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        int i = shortUrl.rfind('/') + 1;
        return m[shortUrl.substr(i, shortUrl.size() - i)];
    }

private:
    unordered_map<string, string> m;
    int idx = 0;
    string domain = "https://tinyurl.com/";
};

// Your Solution object will be instantiated and called as such:
// Solution solution;
// solution.decode(solution.encode(url));

type Codec struct {
	m   map[int]string
	idx int
}

func Constructor() Codec {
	m := map[int]string{}
	return Codec{m, 0}
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
	this.idx++
	this.m[this.idx] = longUrl
	return "https://tinyurl.com/" + strconv.Itoa(this.idx)
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
	i := strings.LastIndexByte(shortUrl, '/')
	v, _ := strconv.Atoi(shortUrl[i+1:])
	return this.m[v]
}

/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * url := obj.encode(longUrl);
 * ans := obj.decode(url);
 */

535 - Encode and Decode TinyURL

535. Encode and Decode TinyURL

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

535. Encode and Decode TinyURL

Level

Description

Solution

All Problems

All Solutions