#535 Encode and Decode TinyURL - Solution

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 <= 10⁴
url is guranteed to be a valid URL.

The core idea behind #535 Encode and Decode TinyURL is to design a system that converts a long URL into a short one and later retrieves the original URL. A common approach is to use a Hash Table to store the mapping between the generated short key and the original long URL.

During encoding, generate a unique identifier (such as an incremental ID or a random string) and transform it into a compact form using techniques like Base62 encoding. This identifier becomes the suffix of the TinyURL. Store the mapping shortKey → longURL in a hash map so it can be retrieved later.

During decoding, extract the key from the short URL and look it up in the hash table to return the stored original URL. Since hash map lookups are constant time on average, both operations remain efficient.

This design ensures fast lookups and minimal collisions while keeping the short URLs compact and unique.

Operation	Time Complexity	Space Complexity
Encode URL	O(1) average	O(n) for storing mappings
Decode URL	O(1) average	O(n)

Solutions (4)

Hash Map Approach

This approach utilizes a hash map (dictionary) where each long URL is stored along with a unique identifier that serves as the short URL.
This method involves two main operations:

Encoding: Generate a unique short URL for each long URL using a sequential counter. Store the mapping in the hash map.
Decoding: Retrieve the original URL using the short URL by referencing the hash map.

Time Complexity: O(1) for both encode and decode operations.
Space Complexity: O(n), where n is the number of URLs encoded.

Python JavaScript

1import random
2import string
3
4class Solution:
5
6    def __init__(self):
7        self.url_map = {}
8        self.code_map = {}
9        self.chars = string.ascii_letters + string.digits
10
11    def encode(self, longUrl: str) -> str:
12        """
13        Encodes a URL to a shortened URL.
14        """
15        code = ''.join(random.choice(self.chars) for _ in range(6))
16        while code in self.code_map:
17            code = ''.join(random.choice(self.chars) for _ in range(6))
18        self.url_map[code] = longUrl
19        self.code_map[longUrl] = code
20        return "http://tinyurl.com/" + code
21
22    def decode(self, shortUrl: str) -> str:
23        """
24        Decodes a shortened URL to its original URL.
25        """
26        code = shortUrl.split("/")[-1]
27        return self.url_map.get(code, "")

Explanation

The encode method generates a 6-character random string for each long URL, stores this mapping in a dictionary, and returns the short URL. The decode method retrieves the original URL using the short URL by referencing the stored dictionary entries. Random generation ensures low collision chances.

Base Conversion Approach

This approach converts a unique identifier into a base62 string, which is used as the short URL.
Using this method involves several steps:

Encoding: Maintain a counter that increments with each URL encoding. Convert this counter using base62 encoding to derive the short URL.
Decoding: Use the base62 string to retrieve the original counter and access the mapped long URL.

Time Complexity: O(log n) for encoding as base conversion takes logn operations. O(1) for decoding.
Space Complexity: O(n), for storing the mappings.

Python Java