LeetCode Solutions Blog

Encode and Decode TinyURL

Difficulty: Medium

Problem Description

Design a class to encode a URL and decode a tiny URL. TinyURL is a URL shortening service where you enter a URL and it returns a short URL. Ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Key Insights

The challenge involves mapping a long URL to a shorter version and vice versa.
A hash table can be used to store the mapping between the long URL and the short URL.
A unique identifier (e.g., a sequence of characters) can be generated for each long URL to create a short URL.
Collision handling may be necessary if two long URLs generate the same short URL.

Space and Time Complexity

Time Complexity: O(1) for both encoding and decoding operations on average, due to hash table operations. Space Complexity: O(n), where n is the number of unique URLs stored in the system.

Solution

The solution employs a hash table (dictionary) to maintain a mapping between the long URL and the short URL. When encoding, a unique short URL is generated (for example, by using a base-62 encoding scheme) and stored in the hash table. When decoding, the short URL is used to retrieve the original long URL from the hash table.

Code Solutions

class Solution:
    def __init__(self):
        self.url_map = {}  # Hash table to store long URL to short URL mapping
        self.base = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789'  # Base62 characters
        self.counter = 0  # Counter to generate unique IDs

    def encode(self, longUrl: str) -> str:
        self.counter += 1  # Increment the counter for a new URL
        shortUrl = self._base62_encode(self.counter)  # Encode counter to a short string
        self.url_map[shortUrl] = longUrl  # Store mapping
        return "http://tinyurl.com/" + shortUrl  # Return the full short URL

    def decode(self, shortUrl: str) -> str:
        shortUrl = shortUrl.split("/")[-1]  # Extract the short URL code
        return self.url_map[shortUrl]  # Retrieve the original long URL

    def _base62_encode(self, num: int) -> str:
        # Converts a number to a base62 string
        encoded = []
        while num > 0:
            encoded.append(self.base[num % 62])  # Get the character for the current digit
            num //= 62  # Reduce the number
        return ''.join(reversed(encoded))  # Return the base62 string