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

LeetCode Problem 535, “Encode and Decode TinyURL,” is a system design problem that requires creating a service similar to TinyURL, which can shorten URLs. The basic idea is to have two functions: one to compress a long URL into a short URL (encode) and another to decode the short URL back into the original long URL. Here’s a general approach to solve this problem in Python:

Approach:

Encode (Shorten URL):
- Convert the long URL into a unique key, which could be a hash or a unique ID.
- Map this unique key to the long URL in a dictionary for later retrieval.
- Return the shortened URL, which is basically the domain followed by the unique key.
Decode (Retrieve Original URL):
- Extract the unique key from the shortened URL.
- Use this key to look up the original URL in the dictionary.
- Return the original URL.

Explanation:

Initialization: urlMap is a dictionary to map a unique key to the long URL. id is a unique identifier for each URL.
Encode: Increment id for each call to ensure uniqueness, then store the long URL with this id in urlMap. Return the shortened URL using a base URL (e.g., ‘http://tinyurl.com/’) combined with the id.
Decode: Extract the unique key from the shortened URL and look up the corresponding long URL in urlMap. Return this long URL.

Note:

This solution uses a simple incremental ID for encoding. In a real-world application, you might use a hash function for better distribution and to handle a larger number of URLs without collisions.
The encode method doesn’t handle the case where the same URL is encoded multiple times; it will get a new short URL each time. Depending on requirements, you may want to modify this behavior.
For real-world usage, considerations like handling invalid URLs, database storage (instead of an in-memory dictionary), and concurrency issues are important.

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.urlMap = {}
        self.id = 0

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL."""
        self.id += 1
        shortUrlKey = str(self.id)
        self.urlMap[shortUrlKey] = longUrl
        return "http://tinyurl.com/" + shortUrlKey

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


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

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

'''
>>> "https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode()
b'https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL'

>>> hashlib.md5("https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode())
<md5 _hashlib.HASH object @ 0x105cb89b0>

>>> hashlib.md5("https://leetcode.ca/2017-05-18-535-Encode-and-Decode-TinyURL".encode()).hexdigest()
'4ee0a628f5bb692be5c56af22bc4ec64'
'''

import hashlib

class Codec: # simple md5 hash
    def __init__(self):
        self.urlMap = {}

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL."""
        # Using MD5 hash for simplicity. You can choose other hash functions as well.
        urlHash = hashlib.md5(longUrl.encode()).hexdigest()[:6]  # Truncate hash for shorter URL
        if urlHash not in self.urlMap:
            self.urlMap[urlHash] = longUrl
        return "http://tinyurl.com/" + urlHash

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


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

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

Approach:

Explanation:

Note:

All Problems

All Solutions

Welcome to Subscribe On Youtube

535. Encode and Decode TinyURL

Level

Description

Solution

Approach:

Explanation:

Note:

All Problems

All Solutions