Leetcode 535. Encode and Decode TinyURL
Problem
We need to design a URL shortening service similar to TinyURL. The service should have the ability to take a long URL like https://leetcode.com/problems/design-tinyurl
and convert it into a short URL like http://tinyurl.com/4e9iAk
and vice versa.
The core of the problem is to implement two simple methods: encode()
which takes a long URL as input and returns a tiny URL and decode()
which takes a tiny URL as input and returns the corresponding original long URL.
Approach
The provided solution, implemented in C++, creates a simple hash-based mapping to associate long URLs to tiny URLs and vice versa. Random characters are used to create the tiny URLs, ensuring that the created tiny URL is unique.
Example
Consider the example where we are given two long URLs to encode: https://leetcode.com/problems/design-tinyurl
and https://leetcode.com/problems/design-urlshortner
.
First, we would encode both URLs:
- Call
encode()
method with the first URL. The method generates a unique code, and maps this code to the same URL, and the URL to this code. Finally, it returns the short/tiny URL.

- Call
encode()
method with the second URL. The logic is similar to the first URL encoding.

At this point, our maps look something like this:
1 2 3codeToUrl = { 4 "4e9iAk" : "https://leetcode.com/problems/design-tinyurl", 5 "5z8xYj" : "https://leetcode.com/problems/design-urlshortner" 6} 7 8urlToCode = { 9 "https://leetcode.com/problems/design-tinyurl" : "4e9iAk", 10 "https://leetcode.com/problems/design-urlshortner" : "5z8xYj" 11}
Solution
C++
1
2cpp
3#include<bits/stdc++.h>
4using namespace std;
5
6class Solution {
7public:
8 string encode(string longUrl) {
9 while (!urlToCode.count(longUrl)) {
10 string code;
11 for (int i = 0; i < 6; ++i)
12 code += alphabets[rand() % alphabets.size()]; // Generate a random 6 character string
13 if (!codeToUrl.count(code)) {
14 codeToUrl[code] = longUrl; // Map the code to the longUrl
15 urlToCode[longUrl] = code; // Map the longUrl to the code
16 return "http://tinyurl.com/" + code;
17 }
18 }
19 throw;
20 }
21
22 string decode(string shortUrl) {
23 return codeToUrl[shortUrl.substr(19)]; // Get and return the long URL by the tiny URL
24 }
25
26private:
27 const string alphabets =
28 "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; // Available characters for the tiny URL
29 unordered_map<string, string> urlToCode; // Map to store long URL to tiny URL mapping
30 unordered_map<string, string> codeToUrl; // Map to store tiny URL to long URL mapping
31};
Note
This problem and solution do not translate directly to Python, Java, JavaScript or C# because those languages do not have similar concepts and structure to C++. Therefore the solution might look different in other languages.# Solution
Python
In Python, the logic is very similar. We use the random
module to generate six random alphanumeric characters, and a pair of dicts, url2code
and code2url
, to store the mappings between long URLs and tiny URLs.
1
2python
3import random
4import string
5
6class Codec:
7 def __init__(self):
8 self.url2code = {}
9 self.code2url = {}
10 self.alphabet = string.ascii_letters + string.digits
11
12 def encode(self, longUrl):
13 while longUrl not in self.url2code:
14 code = ''.join(random.choice(self.alphabet) for _ in range(6))
15 if code not in self.code2url:
16 self.url2code[longUrl] = code
17 self.code2url[code] = longUrl
18 return 'http://tinyurl.com/' + self.url2code[longUrl]
19
20 def decode(self, shortUrl):
21 return self.code2url[shortUrl[-6:]]
JavaScript
Similarly as Python, we can use the JavaScript's built-in Math.random().toString(36)
function to generate the alphabetic characters. For JavaScript, the short URL is obtained using slice()
function instead of substr()
. We use Math.random().toString(36).substr(2,6)
to generate six random alphanumeric characters.
1
2javascript
3var Codec = function() {
4 this.map = new Map();
5 this.alphabet = 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789';
6};
7
8Codec.prototype.encode = function(longUrl) {
9 let key = Array.from({length: 6}, () => this.alphabet[Math.floor(Math.random() * this.alphabet.length)]).join('');
10 this.map.set(key, longUrl);
11 return 'http://tinyurl.com/' + key;
12};
13
14Codec.prototype.decode = function(shortUrl) {
15 let key = shortUrl.slice(-6);
16 return this.map.get(key);
17};
Java
The same pattern applies in Java. Here, it's convenient to use SecureRandom
and StringBuilder
to generate random alphanumeric characters:
1
2java
3import java.util.Map;
4import java.util.HashMap;
5import java.security.SecureRandom;
6
7public class Codec {
8 private static final String alphabet = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
9 private SecureRandom random = new SecureRandom();
10 private Map<String, String> map = new HashMap<>();
11
12 public String encode(String longUrl) {
13 StringBuilder key = new StringBuilder();
14 do {
15 for (int i = 0; i < 6; i++) {
16 key.append(alphabet.charAt(random.nextInt(alphabet.length())));
17 }
18 } while (map.containsKey(key.toString()));
19 map.put(key.toString(), longUrl);
20 return "http://tinyurl.com/" + key.toString();
21 }
22
23 public String decode(String shortUrl) {
24 return map.get(shortUrl.replace("http://tinyurl.com/", ""));
25 }
26}
In the above JavaScript, Python and Java solutions, weโre following a similar approach as the earlier C++ code, to create a simple and intuitive way to solve this problem. The chosen method for encoding and decoding ensures uniqueness of the shortened URL and is about as simple and fast as we could hope for in this kind of application.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.