Encode and Decode TinyURL

Explanation & Solution

Description

Design a URL shortening service like TinyURL. Implement two functions:

encode(longUrl) — Converts a long URL to a shortened URL.
decode(shortUrl) — Converts the shortened URL back to the original long URL.

Your encode and decode functions must be consistent, meaning that calling decode(encode(url)) should always return the original 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 back to the original URL.

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

Output: "https://leetcode.com/problems/design-tinyurl"

Explanation: decode(encode(url)) should return the original URL.

Constraints

1 <= url.length <= 10^4
url is guaranteed to be a valid URL
You may assume that encode will not be called with the same URL twice

Approach

Hash Maps pattern

1. Set Up Data Structures

Create two hash maps: one mapping long URLs to codes, and one mapping codes back to long URLs
Define a character set for generating short codes (alphanumeric)
Define a base URL prefix like http://tinyurl.com/

2. Implement Encode

If the URL has already been encoded, return the existing short URL
Otherwise, generate a random 6-character code from the character set
If the code already exists (collision), regenerate until unique
Store the bidirectional mapping between the long URL and the code
Return the base URL concatenated with the code

3. Implement Decode

Extract the code by removing the base URL prefix from the short URL
Look up the code in the code-to-URL map
Return the original long URL

4. Verify Round-Trip

Calling decode(encode(url)) must always return the original URL
The bidirectional mapping ensures consistency
No information is lost in the encoding process

Key Insight

The hash map provides O(1) lookup for both encoding and decoding
A 6-character alphanumeric code gives 62^6 = ~56.8 billion unique URLs

Time

O(1) average for both encode and decode

Space

O(n) where n is the number of URLs stored

Solution Code

Brick Wall

LRU Cache