Formatted question description: https://leetcode.ca/all/535.html

535. Encode and Decode TinyURL

Level

Medium

Description

Note: This is a companion problem to the System Design problem: Design TinyURL.

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

Use a map to store each encoded short URL and the corresponding long URL before encoding. Maintain a counter count that represents the number of URLs that have been encoded, which is initially 0.

Each time encode is called, increase count by 1, and create the short URL as "http://tinyurl.com/" + count. Map the short URL to the original long URL, and the key-value pair (the key is the short URL and the value is the long URL) is stored in the map.

Each time decode is called, simply obtain the long URL from the map using the short URL as the key.

public class Encode_and_Decode_TinyURL {
    class Codec {
        private static final String BASE_HOST = "http://tinyurl.com/";
        private static final String SEED = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

        // maintain 2 mapping relationships, could be in memory or database or disk file
        private Map<String, String> keyToUrl = new HashMap<>();
        private Map<String, String> urlToKey = new HashMap<>();

        // Encodes a URL to a shortened URL.
        public String encode(String longUrl) {
            if (urlToKey.containsKey(longUrl)) { // could also be collision and hash to different tinyUrl
                return BASE_HOST + urlToKey.get(longUrl);
            }

            String key = null;
            do {
                StringBuilder sb = new StringBuilder();
                for (int i = 0; i < 6; i++) {
                    int r = (int)(Math.random() * SEED.length());
                    sb.append(SEED.charAt(r));
                }
                key = sb.toString();
            } while (keyToUrl.containsKey(key));

            keyToUrl.put(key, longUrl);
            urlToKey.put(longUrl, key);
            return BASE_HOST + key;
        }

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

}

All Problems

All Solutions