Encode and Decode Tiny URL

Design a URL shortener. encode(longUrl) returns a short URL, and decode(shortUrl) returns the original long URL. Any scheme is allowed, as long as decoding a short URL produced by the same object gives back the original. This is LeetCode 535.

Example 1
Input: url = "https://cscode.io/algo/strings/EncodeDecodeTinyURL"
Output: "https://cscode.io/algo/strings/EncodeDecodeTinyURL"
Explanation: decode(encode(url)) must return the same URL.

How to Think About It

Step 1: The short URL is a key into a table

The short URL does not need to contain the long one. It only needs to be a unique key; the object keeps a map from key to long URL, and decoding is a lookup.

Step 2: Make keys from a counter

Give each new URL the next number from a counter: 1, 2, 3, ... Numbers never repeat, so keys never collide. Random keys also work, but then you must check for collisions.

Step 3: Keep keys short with base 62

Writing the counter in base 62, using the digits 0-9, a-z and A-Z, keeps keys short: six characters cover 626, about 56 billion URLs.

Step 4: Same long URL, same short URL

A second map from long URL to key means encoding the same URL twice returns the same short URL, instead of using up a new key.

Walkthrough

CallCounterKeyReturns
encode("https://cscode.io/algo/")11http://tinyurl.com/1
encode("https://cscode.io/java/")22http://tinyurl.com/2
encode("https://cscode.io/algo/")already known1http://tinyurl.com/1
decode("http://tinyurl.com/2")2https://cscode.io/java/

The 62nd URL gets the key "Z", and the 63rd gets "10".

Java Solution

The two maps make both directions O(1); toBase62 turns the counter into a short key.

Java
import java.util.HashMap;
import java.util.Map;

public class EncodeDecodeTinyURL {

    private static final String BASE = "http://tinyurl.com/";
    private static final String DIGITS =
            "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

    private final Map<String, String> codeToUrl = new HashMap<>();
    private final Map<String, String> urlToCode = new HashMap<>();
    private long nextId = 1;

    public String encode(String longUrl) {
        String code = urlToCode.get(longUrl);
        if (code == null) {
            code = toBase62(nextId++);        // a new, never-used short code
            codeToUrl.put(code, longUrl);
            urlToCode.put(longUrl, code);
        }
        return BASE + code;
    }

    public String decode(String shortUrl) {
        return codeToUrl.get(shortUrl.substring(BASE.length()));
    }

    private static String toBase62(long n) {
        StringBuilder sb = new StringBuilder();
        while (n > 0) {
            sb.append(DIGITS.charAt((int) (n % 62)));
            n /= 62;
        }
        return sb.reverse().toString();
    }

    public static void main(String[] args) {
        EncodeDecodeTinyURL codec = new EncodeDecodeTinyURL();
        String url = "https://cscode.io/algo/strings/EncodeDecodeTinyURL";
        String tiny = codec.encode(url);
        System.out.println(tiny);                          // http://tinyurl.com/1
        System.out.println(codec.decode(tiny).equals(url));   // true
    }
}

The original implementation, EncodeDecodeTinyURL.java, is on GitHub.

Complexity

  • Time: O(L) per call, where L is the URL length (for hashing it); the base-62 conversion is O(log of the counter).
  • Space: O(total length of the URLs stored).

A real service would store the table in a database and hand out ranges of the counter to each server. For encoding a whole list into one string, see Encode and Decode Strings.