Sponsored
Sponsored
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:
Time Complexity: O(1) for both encode and decode operations.
Space Complexity: O(n), where n is the number of URLs encoded.
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, "")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.
This approach converts a unique identifier into a base62 string, which is used as the short URL.
Using this method involves several steps:
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.
1import java.util.*;
2
This Java solution employs a counter stored in a map, incremented on each URL encoding, and converted to a base62 identifier. The decode method extracts the identifier from the short URL to restore the original URL.