Want Help Cracking FAANG?

(Then click this)

 ×
Back to Question Bank

535. Encode and Decode TinyURL - Leetcode Solution

Code Implementation

import random
import string

class Codec:
    def __init__(self):
        self.url2code = {}
        self.code2url = {}
        self.chars = string.ascii_letters + string.digits
        self.prefix = "http://tinyurl.com/"
    
    def encode(self, longUrl: str) -> str:
        if longUrl in self.url2code:
            return self.prefix + self.url2code[longUrl]
        while True:
            code = ''.join(random.choices(self.chars, k=6))
            if code not in self.code2url:
                break
        self.code2url[code] = longUrl
        self.url2code[longUrl] = code
        return self.prefix + code

    def decode(self, shortUrl: str) -> str:
        code = shortUrl.replace(self.prefix, '')
        return self.code2url.get(code, "")
      
class Solution {
public:
    unordered_map<string, string> code2url, url2code;
    string chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    string prefix = "http://tinyurl.com/";

    string getCode() {
        string code = "";
        for (int i = 0; i < 6; ++i) {
            code += chars[rand() % chars.size()];
        }
        return code;
    }

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        if (url2code.count(longUrl)) {
            return prefix + url2code[longUrl];
        }
        string code = getCode();
        while (code2url.count(code)) {
            code = getCode();
        }
        code2url[code] = longUrl;
        url2code[longUrl] = code;
        return prefix + code;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        string code = shortUrl.substr(prefix.size());
        if (code2url.count(code)) return code2url[code];
        return "";
    }
};
      
public class Codec {
    Map<String, String> code2url = new HashMap<>();
    Map<String, String> url2code = new HashMap<>();
    String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    String prefix = "http://tinyurl.com/";
    Random rand = new Random();

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (url2code.containsKey(longUrl)) {
            return prefix + url2code.get(longUrl);
        }
        String code;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; ++i) {
                sb.append(chars.charAt(rand.nextInt(chars.length())));
            }
            code = sb.toString();
        } while (code2url.containsKey(code));
        code2url.put(code, longUrl);
        url2code.put(longUrl, code);
        return prefix + code;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        String code = shortUrl.replace(prefix, "");
        return code2url.getOrDefault(code, "");
    }
}
      
var Codec = function() {
    this.code2url = {};
    this.url2code = {};
    this.chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
    this.prefix = 'http://tinyurl.com/';
};

Codec.prototype.encode = function(longUrl) {
    if (this.url2code[longUrl]) {
        return this.prefix + this.url2code[longUrl];
    }
    let code = '';
    do {
        code = '';
        for (let i = 0; i < 6; ++i) {
            code += this.chars[Math.floor(Math.random() * this.chars.length)];
        }
    } while (this.code2url[code]);
    this.code2url[code] = longUrl;
    this.url2code[longUrl] = code;
    return this.prefix + code;
};

Codec.prototype.decode = function(shortUrl) {
    let code = shortUrl.replace(this.prefix, '');
    return this.code2url[code] || '';
};

Problem Description

The "Encode and Decode TinyURL" problem asks you to design a system that can encode a long URL into a shortened URL (like TinyURL) and decode it back to the original. You must 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.
Key constraints:
  • There is always exactly one valid mapping for each input URL.
  • Do not reuse short codes for different URLs.
  • Short URLs should be as short as possible and unique.
  • Your solution should not rely on any external database or persistent storage.

Thought Process

At first glance, one might think of simply hashing the URL or using a counter to generate short URLs. However, collisions (two URLs mapping to the same short code) or predictability (sequential codes being guessable) are concerns. Furthermore, we need to ensure that each long URL always maps to the same short URL, and that decoding is always possible.

A brute-force approach could be to store a mapping of every long URL to a unique short code in a dictionary or hashmap. However, if we want the short URL to be as short as possible and unique, we need to generate a random code of fixed length (e.g., 6 characters) using a set of allowed characters.

To optimize:
  • Use hash maps for O(1) lookup and insertion.
  • Generate random codes and check for uniqueness to avoid collisions.
  • Ensure that the same long URL always gets the same short code.

Solution Approach

The solution involves designing an encoder and a decoder using two hash maps:
  • url2code: Maps the original long URL to its generated short code.
  • code2url: Maps the generated short code back to the original long URL.
  1. When encoding, first check if the long URL already has a code. If so, return the existing short URL.
  2. If not, generate a new random 6-character code using allowed characters (letters and digits).
  3. Check if this code is already in use (to avoid collisions). If yes, repeat until a unique code is found.
  4. Store the mappings in both hash maps.
  5. Return the short URL, which is a fixed prefix plus the generated code.
  6. For decoding, extract the code from the short URL and look up the original URL in code2url.
This approach ensures:
  • Uniqueness of short codes.
  • Constant time encoding and decoding.
  • Idempotency (encoding the same long URL always returns the same short URL).

Example Walkthrough

Let's walk through an example:
  • Input: encode("https://leetcode.com/problems/design-tinyurl")
  • Suppose the random code generated is abc123.
  • We store the mapping:
    • url2code["https://leetcode.com/problems/design-tinyurl"] = "abc123"
    • code2url["abc123"] = "https://leetcode.com/problems/design-tinyurl"
  • The function returns "http://tinyurl.com/abc123".
  • Decoding: decode("http://tinyurl.com/abc123")
  • We extract "abc123" and look it up in code2url to get the original URL.
If we encode the same URL again, we simply return the same short URL because of the url2code mapping.

Time and Space Complexity

  • Brute-force approach: If we tried to scan all possible codes for each encode/decode, time would be O(N) per operation, which is inefficient.
  • Optimized (hash map) approach:
    • Encoding: O(1) average time (hash map insertion/lookup and random code generation are constant on average).
    • Decoding: O(1) average time (hash map lookup).
    • Space: O(N), where N is the number of unique URLs encoded (for storing the mappings).
The random code generation is efficient because the space of 6-character codes is very large (~56 billion), making collisions extremely unlikely for practical use.

Summary

In summary, the solution leverages hash maps to maintain fast and unique mappings between long URLs and short codes. By generating random codes and ensuring uniqueness, we avoid collisions and keep the short URLs compact. The approach is efficient, easy to implement, and mirrors how real-world URL shorteners work in practice, making it both practical and elegant.