deepSWE.io

Encode and Decode TinyURL

Hashing

20 min

Problem Statement

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.

Example

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"

Output: "http://tinyurl.com/4e9iAk"

Solution (Two Hash Maps)

We can use two hash maps to store the mappings from long URL to short URL and vice-versa. This allows for O(1) time complexity for both encoding and decoding.

Algorithm Steps

Initialize two hash maps: `encodeMap` and `decodeMap`.
For `encode`, if the long URL is not in `encodeMap`, generate a new short URL. A simple way is to use a counter.
Store the mapping in both hash maps.
For `decode`, simply return the long URL from `decodeMap`.

Long URL:

Long URL

↔

Short URL

Enter a URL and click play to encode.

URL Mappings

Encode and Decode TinyURL Solution


class Codec:
    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.encodeMap:
            shortUrl = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = shortUrl
            self.decodeMap[shortUrl] = longUrl
        return self.encodeMap[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.decodeMap[shortUrl]