535. Encode and Decode TinyURL

MediumDesignHash TableStringHash Function
Leetcode Link

Problem Description

The problem asks us to design a system that can encode a long URL into a short URL and decode it back to the original URL. This is similar to services like TinyURL that make long URLs more manageable and easier to share. The problem specifically requires implementing a class with two methods: one to encode a URL and one to decode a previously encoded URL.

Intuition

To solve this problem, we need to establish a system that can map a long URL to a unique short identifier and be able to retrieve the original URL using that identifier. The core idea behind the solution is to use a hash map (or dictionary in Python) to keep track of the association between the encoded short URLs and the original long URLs.

Here's the step-by-step reasoning for arriving at the solution:

  1. Encoding:

    • Each time we want to encode a new URL, we increment an index that acts as a unique identifier for each URL.
    • Then, we add an entry to our hash map where the key is the string representation of the current index and the value is the long URL.
    • The encoded tiny URL is generated by concatenating a predefined domain (e.g., "https://tinyurl.com/") with the index.
  2. Decoding:

    • To decode, we can extract the index from the end of the short URL. This index is the key to our hash map.
    • We then use this key to look up the associated long URL in our hash map and return it.

This approach efficiently encodes and decodes URLs using the methods encode and decode, assuming no two URLs will be encoded at the same index.

Solution Approach

The implementation uses a simple yet effective approach, based on a hash map and an incremental counter to correlate long URLs with their tiny counterparts.

Data Structures:

  • Hash Map (defaultdict in Python): A hash map is used to store and quickly retrieve the association between the unique identifier (idx) and the original long URL.

Algorithm:

The codec class is implemented in Python with the following methods:

  1. Initialization (__init__):

    • A hash map self.m is initialized to store the mapping between a short URL suffix (a unique index) and the original long URL.
    • self.idx is initialized to 0 which is used as a counter to create unique identifiers for each URL.
  2. Encode Method (encode):

    • Increment the self.idx counter to generate a new unique identifier for a new long URL.
    • Store the long URL in the hash map with the string representation of the incremental index as the key.
    • Generate the tiny URL by concatenating the predefined domain self.domain with the current index.
    • Return the full tiny URL.

    The encode function can be articulated with a small formula where longUrl is mapped to "https://tinyurl.com/" + str(self.idx).

    1self.idx += 1
    2self.m[str(self.idx)] = longUrl
    3return f'{self.domain}{self.idx}'
  3. Decode Method (decode):

    • Extract the unique identifier from the short URL by splitting it at the '/' and taking the last segment.
    • The identifier is then used to find the original long URL from the hash map.
    • Return the long URL.

    This process can be described as retrieving self.m[idx], where idx is the last part of shortUrl.

    1idx = shortUrl.split('/')[-1]
    2return self.m[idx]

Patterns:

  • Unique Identifier: By using a simple counter, each URL gets a unique identifier which essentially works as a key, preventing collisions between different long URLs. DbSetti does not rely on hashing functions or complex encoding schemes, reducing overhead and complexity.
  • Direct Mapping: The system relies on direct mappings from unique identifiers to original URLs, allowing O(1) time complexity for both encoding and decoding functions.

This straightforward approach is easy to understand and implement, requiring only basic data manipulation. It does not involve any complex hash functions, avoids collisions, and ensures consistent O(1) performance for basic operations.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's demonstrate the encoding and decoding process with a simple example:

Imagine we have the following URL to encode: https://www.example.com/a-very-long-url-with-multiple-sections.

After we initiate our codec class, it might look something like this:

1class Codec:
2    def __init__(self):
3        self.m = {}
4        self.idx = 0
5        self.domain = "https://tinyurl.com/"
6  
7    def encode(self, longUrl):
8        # Increment the index to create a new identifier
9        self.idx += 1
10        # Map the current index to the long URL
11        self.m[str(self.idx)] = longUrl
12        # Generate and return the shortened URL
13        return f'{self.domain}{self.idx}'
14  
15    def decode(self, shortUrl):
16        # Extract the identifier from the URL
17        idx = shortUrl.split('/')[-1]
18        # Retrieve the original long URL
19        return self.m[idx]

Let's go through the actual encoding and decoding steps with our example URL:

  1. Encoding the URL:

    • We take the long URL https://www.example.com/a-very-long-url-with-multiple-sections.
    • Since self.idx starts at 0, after encoding our first URL, it will become 1.
    • We add the long URL to the hash map with the key '1'.
    • The method encode returns a tiny URL, which will be "https://tinyurl.com/1".
  2. Decoding the URL:

    • Now, when we want to access the original URL, we take the tiny URL "https://tinyurl.com/1".
    • The method decode will extract the identifier '1' which is the last segment after splitting the URL by '/'.
    • It will then look up this index in our hash map to find the original URL, which is https://www.example.com/a-very-long-url-with-multiple-sections.
    • The decode method will return this long URL.

By following this simple example, we've seen how the unique identifier helps in associating a long URL with a shortened version, and how easy it becomes to retrieve the original URL when needed. Each encode operation generates a new, unique tiny URL, and each decode operation precisely retrieves the corresponding original URL using this mechanism.

Python Solution

1from collections import defaultdict
2
3class Codec:
4    def __init__(self):
5        # Initialize a dictionary to store the long URL against unique indexes
6        self.url_mapping = defaultdict()
7        self.index = 0  # A counter to create unique keys for URL
8        self.domain = 'https://tinyurl.com/'  # The domain prefix for the short URL
9
10    def encode(self, longUrl: str) -> str:
11        """Encodes a URL to a shortened URL."""
12        # Increment the index to get a unique key for a new URL
13        self.index += 1
14        # Store the long URL in the dictionary with the new index as key
15        self.url_mapping[str(self.index)] = longUrl
16        # Return the domain concatenated with the unique index
17        return f'{self.domain}{self.index}'
18
19    def decode(self, shortUrl: str) -> str:
20        """Decodes a shortened URL to its original URL."""
21        # Extract the index from the short URL by splitting on '/'
22        index = shortUrl.split('/')[-1]
23        # Use the index to retrieve the corresponding long URL from the dictionary
24        return self.url_mapping[index]
25
26
27# Example of Usage:
28# codec = Codec()
29# short_url = codec.encode("https://www.example.com")
30# print(codec.decode(short_url))
31

Java Solution

1import java.util.HashMap;
2import java.util.Map;
3
4public class Codec {
5    // Map to store the index-to-URL mappings
6    private Map<String, String> indexToUrlMap = new HashMap<>();
7
8    // Counter to generate unique keys for shortened URLs
9    private int indexCounter = 0;
10
11    // Domain to prepend to the unique identifier creating the shortened URL
12    private String domain = "https://tinyurl.com/";
13
14    /**
15     * Encodes a URL to a shortened URL.
16     * @param longUrl The original long URL to be encoded
17     * @return The encoded short URL
18     */
19    public String encode(String longUrl) {
20        // Increment the indexCounter to get a unique key for this URL
21        String key = String.valueOf(++indexCounter);
22        // Store the long URL with the generated key in the map
23        indexToUrlMap.put(key, longUrl);
24        // Return the complete shortened URL by appending the key to the domain
25        return domain + key;
26    }
27
28    /**
29     * Decodes a shortened URL to its original URL.
30     * @param shortUrl The shortened URL to be decoded
31     * @return The original long URL
32     */
33    public String decode(String shortUrl) {
34        // Find the position just after the last '/' character in the shortened URL
35        int index = shortUrl.lastIndexOf('/') + 1;
36        // Extract the key from the short URL and look it up in the map to retrieve the original URL
37        String key = shortUrl.substring(index);
38        return indexToUrlMap.get(key);
39    }
40}
41
42// The Codec class may be used as follows:
43// Codec codec = new Codec();
44// String shortUrl = codec.encode("https://www.example.com");
45// String longUrl = codec.decode(shortUrl);
46

C++ Solution

1#include <string>
2#include <unordered_map>
3
4class Solution {
5public:
6    // Encodes a URL to a shortened URL.
7    std::string encode(std::string longUrl) {
8        // Convert the current counter value to a string to create a unique key
9        std::string key = std::to_string(++counter);
10      
11        // Associate the key with the original long URL in the hashmap
12        urlMap[key] = longUrl;
13      
14        // Construct the short URL by appending the key to the predefined domain
15        return domain + key;
16    }
17
18    // Decodes a shortened URL to its original URL.
19    std::string decode(std::string shortUrl) {
20        // Find the position of the last '/' in the short URL
21        std::size_t lastSlashPos = shortUrl.rfind('/') + 1;
22
23        // Extract the key from the short URL based on the position of the last '/'
24        // and use it to retrieve the original long URL from the hashmap
25        return urlMap[shortUrl.substr(lastSlashPos, shortUrl.size() - lastSlashPos)];
26    }
27
28private:
29    // Hashmap to store the association between the unique key and the original long URL
30    std::unordered_map<std::string, std::string> urlMap;
31
32    // Counter to generate unique keys for each URL encoded
33    int counter = 0;
34
35    // The base domain for the shortened URL
36    std::string domain = "https://tinyurl.com/";
37};
38
39// Usage example:
40// Solution solution;
41// std::string shortUrl = solution.encode("https://example.com");
42// std::string longUrl = solution.decode(shortUrl);
43

Typescript Solution

1// Import necessary components for working with maps
2import { URL } from "url";
3
4// Create a Map to store the association between the unique key and the original long URL
5const urlMap = new Map<string, string>();
6
7// Declare a counter to generate unique keys for each URL encoded
8let counter: number = 0;
9
10// Define the base domain for the shortened URL
11const domain: string = "https://tinyurl.com/";
12
13// Encodes a URL to a shortened URL.
14function encode(longUrl: string): string {
15    // Convert the current counter value to a string to create a unique key
16    counter++;
17    const key: string = counter.toString();
18  
19    // Associate the key with the original long URL in the map
20    urlMap.set(key, longUrl);
21  
22    // Construct the short URL by appending the key to the predefined domain
23    return domain + key;
24}
25
26// Decodes a shortened URL to its original URL.
27function decode(shortUrl: string): string {
28    // Find the position of the last '/' in the short URL using URL class
29    const shortUrlObj = new URL(shortUrl);
30    const key: string = shortUrlObj.pathname.substring(1); // Remove the leading '/'
31  
32    // Use the key to retrieve the original long URL from the map
33    const longUrl: string | undefined = urlMap.get(key);
34    if (longUrl) {
35        return longUrl;
36    } else {
37        throw new Error("Short URL does not correspond to a known long URL");
38    }
39}
40
41// Note: Usage example is not included as we are defining things in the global scope
42

Time and Space Complexity

Time Complexity

  • encode: The encode method has a time complexity of O(1) because it only performs simple arithmetic incrementation and one assignment operation, neither of which depend on the size of the input.

  • decode: The decode method has a time complexity of O(1) because it performs a split operation on a URL which is a constant time operation since the URL length is fixed ("https://tinyurl.com/" part), and a dictionary lookup, which is generally considered constant time given a good hash function and well-distributed keys.

Space Complexity

  • The space complexity of the overall Codec class is O(N) where N is the number of URLs encoded. This is because each newly encoded URL adds one additional entry to the dictionary (self.m), which grows linearly with the number of unique long URLs processed.
😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫