Encode and Decode TinyURL LeetCode

Lengthy URLs can be quite a hassle, as they’re typically difficult to remember. Their cluttered look is unorganized, which can adversely affect a user’s perception of the website. URL shortener algorithm solves this issue by encoding these longer URLs into shorter ones. TinyURL is the most popular service for this purpose.

Key takeaways:
TinyURL is a URL shortening service that converts long URLs into shorter, more manageable links.
The TinyURL LeetCode challenge involves creating functions to encode and decode URLs efficiently to ensure unique and reversible mappings.
Using a unique identifier for each original URL is crucial for accurate decoding.
Optimal algorithms for URL encoding and decoding utilize data structures like hash maps for quick insertions and lookups.
The time complexity for URL encoding and decoding is typically $O(1)$ , making it efficient for real-time applications.

What is TinyURL?

TinyURL employs a unique approach to generating shortened links. Instead of following the traditional DNS resolution process, it creates distinct URL identifiers through hashing. When a user clicks on a TinyURL, they are redirected to the original content stored in TinyURL’s database. This method allows for the creation of user-friendly links while keeping the DNS process unchanged.

Note: The conventional URLs are translated to the IP address through the DNS on request of the browser, but tiny URLs work differently. It follows the redirection approach instead of following the DNS process. When a user clicks on the tiny URL, it is redirected to the real link saved in the TinyURL database. This way, TinyURLs generate short and user-friendly links, keeping the DNS process unchanged.

Problem statement

This problem is related to encode and decode URLs and consists of the following two parts:

Encoding a lengthy URL into a unique, shortened one.
Decoding the shortened URL back into its original form.

Note: In TinyURL’s case, the base URL is https://tinyurl.com/, and the encoded characters are appended. We'll also use the hashlib library for our hashing purposes.

The diagram below illustrates the URL encoding and decoding.

Intuition

The main idea behind this algorithm is to simplify long and complex URLs into shorter, more manageable links while maintaining a connection to the original URLs. By using a hashing technique, we can create unique identifiers for each original URL, allowing us to store and retrieve them efficiently.

If you’re interested in solving more challenging problems related to encoding and decoding, check out the Decode Ways and Group Anagrams problems.

Algorithm

This algorithm for the TinyURL LeetCode problem to encode and decode URLs consists of the following key components:

Initialization: The class initializes with an empty hashmap to store the relationship between original URLs and their corresponding encoded versions.
encode: This takes an original URL and encodes it using MD5 hashing to generate a unique code of $7$ characters. The method constructs a new URL by appending the unique code to the base URL (self.base). It maps the new URL to the original URL in the hashmap and returns the shortened URL.
decode: This takes a shortened URL and checks if it exists in the hashmap. If found, retrieve the original URL from the hashmap. If not found, returns a message indicating that the URL isn’t in the map.

import hashlib
class TinyURL:
    def __init__(self):
        self.hashmap = {}  # Dictionary to store short-to-long URL mappings
        self.base = "https://tinyurl.com/"  # Base URL for shortened links
    def encode(self, original_url):
        """
        Encodes a long URL into a short URL using MD5 hashing.
        """
        hashed = hashlib.md5(original_url.encode())  # Generate MD5 hash
        code = hashed.hexdigest()[:7]  # Get first 7 characters as short code
        encoded_url = self.base + code  # Create short URL
        self.hashmap[encoded_url] = original_url  # Store mapping
        return encoded_url
    def decode(self, encoded_url):
        """
        Decodes a short URL back to its original long URL.
        """
        if encoded_url in self.hashmap:
            return self.hashmap[encoded_url]  # Return original URL if found
        else:
            return "URL isn't present in the map"  # Error if not found
# Example usage
original_url = "https://www.example.com/this-is-an-example-URL"
print("Original URL: ", original_url)
obj = TinyURL()
encoded_url = obj.encode(original_url)
print("Encoded URL:  ", encoded_url)
decoded_url = obj.decode(encoded_url)
print("Decoded URL:  ", decoded_url)

Code explanation

Line 1: Import the hashlib library.
Line 3: Define the TinyURL class that contains both encode and decode functions.
Line 5: Define a dictionary called hashmap, which stores all shortened URLs with their original forms.
Line 6: Define the base attribute, which is the prefix all of the encoded URLs will share. In this case, it is https://tinyurl.com/.
Line 8: Define the encode function that takes the original URL as a parameter.
Lines 12–16: Use the hashlib.md5 method to hash the URL. We then obtain a hexadecimal representation of the hash using the hexdigest() method stored in the code variable. Here, we use [:7] to obtain a slice of the first seven elements of the hash. The value of this shortened URL is then stored in hashmap alongside its original version.
Line 18: Define the decode function, which takes the encoded URL as a parameter.
Line 22–25: Check whether the encoded URL is present in the dictionary. If it is, we return its corresponding original URL from the hashmap. If not, we return a string stating that the value isn’t in our dictionary.
Lines 30–38: Create the TinyUrl class object, and use it to call the encode and decode functions to encode and decode original_url, respectively.

Time complexity

Both encoding and decoding are not influenced by the number of previously encoded or decoded URLs, resulting in a constant time complexity for each operation. Therefore, the time complexity of both encode and decode is $O(1)$ .

Space complexity

The space complexity of this algorithm is $O(n)$ , where $n$ is the number of unique URLs encoded, directly correlating with the size of the hashmap storing the mappings between shortened and original URLs.

To practice more LeetCode coding problems similar to Encode and Decode TinyURL, check out the best-selling Grokking the Coding Interview Patterns series. One of the standout features of this series is that it’s offered in six different programming languages.

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What are the key operations required for a URL shortener?

A URL shortener typically requires two main operations: encoding a long URL into a short one and decoding the short URL back to the original.

What data structures are commonly used for implementing a URL shortener?

Hashmaps (or dictionaries) are commonly used to store the mapping between shortened URLs and their corresponding original URLs for efficient retrieval.

Can I implement URL shortening in multiple programming languages?

Yes, you can implement the encode and decode TinyURL problem in various programming languages, including Python, Java, and C++.

What are some similar problems to encode and decode TinyURL on LeetCode?

Similar problems include Decode Ways, Group Anagrams, and String Compression, which also focus on string manipulation and encoding.

How can I effectively use LeetCode to prepare for coding interviews?

To prepare effectively, start by focusing on the most common topics asked in interviews, such as data structures, algorithms, and system design. Use LeetCode’s filters to practice problems by difficulty and topic, and take advantage of the discussion forums for insights and solutions.

Free Resources