How do you solve Encode and Decode TinyURL on LeetCode?

Encode and Decode TinyURL (LeetCode #535) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(1) time complexity and O(n) space complexity. Key insight: Using a hash map allows for efficient storage and retrieval of URLs.

What is the brute force solution for Encode and Decode TinyURL?

The brute force approach for Encode and Decode TinyURL is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves creating a mapping between the long URL and a short URL using a simple string manipulation. We can generate a short URL by appending a unique identifier to a base URL. The optimal Optimal Solution approach improves this to O(1).

What algorithm or data structure is used to solve Encode and Decode TinyURL?

Encode and Decode TinyURL uses the following concepts: Hash Table, String, Design, Hash Function. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Encode and Decode TinyURL?

Clearly explain your thought process while coding. Discuss potential edge cases and how you would handle them. Be prepared to optimize your solution after presenting the brute force approach.

What are common mistakes when solving Encode and Decode TinyURL?

Not handling edge cases, such as duplicate URLs. Failing to ensure the uniqueness of the short URL.

#535

Encode and Decode TinyURL

Medium

Hash TableStringDesignHash FunctionHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(1)
Space	O(1)	O(n)

💡

Intuition

Time O(1)Space O(n)

The optimal solution uses a hash map to store the mapping of short URLs to long URLs, allowing for O(1) average time complexity for both encoding and decoding operations. This approach ensures that we can efficiently manage the URL mappings.

⚙️

Algorithm

4 steps

1Step 1: Initialize a hash map to store the mapping of short URLs to long URLs.
2Step 2: Use a counter to generate unique identifiers for short URLs.
3Step 3: When encoding, generate a short URL by appending the counter to a base URL and store the mapping in the hash map.
4Step 4: When decoding, retrieve the long URL directly from the hash map using the short URL.

solution.py14 lines

1class Solution:
2    def __init__(self):
3        self.url_map = {}
4        self.base_url = 'http://tinyurl.com/'
5        self.counter = 0
6
7    def encode(self, longUrl: str) -> str:
8        self.counter += 1
9        shortUrl = self.base_url + str(self.counter)
10        self.url_map[shortUrl] = longUrl
11        return shortUrl
12
13    def decode(self, shortUrl: str) -> str:
14        return self.url_map[shortUrl]

ℹ

Complexity note: The time complexity is O(1) for both encoding and decoding because we are using a hash map for direct lookups. The space complexity is O(n) because we store each long URL in the hash map.

1Using a hash map allows for efficient storage and retrieval of URLs.
2Generating unique identifiers is crucial for ensuring that each short URL maps to a unique long URL.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.