Encode and Decode TinyUrl

Problem

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

Solution

Two HashMap Solution: O(n) time, O(n) space

public class Codec {

    Map<String, String> urlMapTiny = new HashMap<>();
    Map<String, String> tinyMapUrl = new HashMap<>();

    final String CODES = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM";
    final String BASE_URL = "http://tinyurl.com/";

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (urlMapTiny.containsKey(longUrl)) return urlMapTiny.get(longUrl);
        String tinyUrl = "";
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                sb.append(CODES.charAt((int) Math.random() * CODES.length()));
            }
            tinyUrl = sb.toString();
        } while (tinyMapUrl.containsKey(tinyUrl));
        urlMapTiny.put(longUrl, BASE_URL + tinyUrl);
        tinyMapUrl.put(tinyUrl, longUrl);
        return tinyUrl;
    } 

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return tinyMapUrl.get(shortUrl.replace(BASE_URL, ""));
    }
}

Analysis

We use two hash maps to encode and decode
Notice that when we are encoding, we need to make sure the tinyUrl is unique
We accomplish this by using do while() loop
Inside the loop, we construct the tinyUrl by Math.random() * CODES.length()
Also notice that in decode() we need to remove BASE_URL cause we does not store it in our tinyUrl

results matching ""

    No results matching ""