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:

1. 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.

2. 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.