Introduction

In this blog post, we will explore how to solve the LeetCode problem "535" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

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 a class to encode a URL and decode a tiny URL. 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. Implement the Solution class: Solution() Initializes the object of the system. String encode(String longUrl) Returns a tiny URL for the given longUrl. String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object. Example 1: Input: url = "https://leetcode.com/problems/design-tinyurl" Output: "https://leetcode.com/problems/design-tinyurl" Explanation: Solution obj = new Solution(); string tiny = obj.encode(url); // returns the encoded tiny url. string ans = obj.decode(tiny); // returns the original url after decoding it. Constraints: 1 <= url.length <= 104 url is guranteed to be a valid URL.

Explanation

Here's a solution to the TinyURL problem, focusing on efficiency and clarity:

• Hashing: Use a dictionary (hash map) to store the mapping between short URLs and long URLs.
• Unique Short URLs: Generate unique short URLs (e.g., using a counter and base-62 encoding).

• Bi-directional Mapping: Store both the short-to-long and long-to-short mappings for faster lookups in both encode and decode.

• Runtime Complexity: O(1) for both encode and decode on average. Storage Complexity: O(n), where n is the number of URLs stored.

Code

    class Solution:
    def __init__(self):
        self.url_to_tiny = {}
        self.tiny_to_url = {}
        self.counter = 0
        self.base = 62
        self.alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        self.tiny_url_prefix = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        if longUrl in self.url_to_tiny:
            return self.url_to_tiny[longUrl]

        self.counter += 1
        n = self.counter
        tiny_url_code = ""
        while n > 0:
            tiny_url_code = self.alphabet[n % self.base] + tiny_url_code
            n //= self.base

        shortUrl = self.tiny_url_prefix + tiny_url_code
        self.url_to_tiny[longUrl] = shortUrl
        self.tiny_to_url[shortUrl] = longUrl
        return shortUrl

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.tiny_to_url[shortUrl]


# Your Solution object will be instantiated and called as such:
# sol = Solution()
# print(sol.encode(longUrl))
# print(sol.decode(shortUrl))