Encode and Decode TinyURL

Problem Statement

In the realm of URL shortening services, TinyURL stands out by converting a lengthy URL into a much shorter version that is easier to share and manage. The task involves designing a Solution class capable of encoding a long URL to a tiny URL and then decoding it back to its original form.

This service allows you to submit a long URL such as https://vultr.com/problems/design-tinyurl, which it then transforms into significantly shortened variants like http://tinyurl.com/4e9iAk. The main challenge is to ensure that every encoded URL can be perfectly decoded to its original form, adhering to the integrity of the data.

The Solution class should have:

• A constructor Solution(), which sets up the system for operation.
• A method String encode(String longUrl), which takes a long URL and returns its shortened version.
• A method String decode(String shortUrl), which retrieves the original URL using the short URL provided.

The guarantee provided is that the short URL to be decoded has been encoded by the same instance of the solution class, ensuring a consistent encoding-decoding lifecycle.

Examples

Example 1

Input:

url = "https://vultr.com/problems/design-tinyurl"

Output:

"https://vultr.com/problems/design-tinyurl"

Explanation:

Solution obj = new Solution();
string tiny = obj.encode(url); // returns the encoded tiny url.
string ans = obj.decode(tiny); // returns the original url after decoding it.

Constraints

• 1 <= url.length <= 104
• url is guranteed to be a valid URL.

Approach and Intuition

Given the specifications and examples, the mechanisms of encoding and decoding URLs can be understood and tackled in several intuitive steps:

1. Initialization of Data Structure:

   • Instantiate a mapping or data structure that efficiently links the long URLs to their corresponding shortened versions. This structure must be bidirectional to allow reverse look-up during decoding.

2. Encoding Process:

   • Derive a unique identifier or hash for the given long URL. These identifiers should be short, making sure they conserve space—a crucial feature for a URL shortener.
   • Map the long URL to this unique tiny URL in the data structure.
   • Return the tiny version of the URL.

3. Decoding Process:

   • Use the mapped data structure to retrieve the original URL using the shortened version as a key.
   • This unidirectional lookup should yield the original URL as long as the shortened URL is valid and was generated by the system.

The constraints provided include:

• The minimum and maximum lengths for a URL, ensuring that the algorithm copes well with various sizes of input.
• Ensuring the original URLs are indeed valid URLs, eliminating the need for validation checks before processing.

This structured way of handling URL encoding ensures that each URL transformed into its shortened form can be reliably converted back, maintaining the usefulness and reliability of the service.

Solutions

public class URLShortener {
    String validChars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    HashMap<String, String> urlMap = new HashMap<>();
    Random random = new Random();
    String shortKey = generateRandomKey();

    public String generateRandomKey() {
        StringBuilder keyBuilder = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            keyBuilder.append(validChars.charAt(random.nextInt(62)));
        }
        return keyBuilder.toString();
    }

    public String encode(String originalUrl) {
        while (urlMap.containsKey(shortKey)) {
            shortKey = generateRandomKey();
        }
        urlMap.put(shortKey, originalUrl);
        return "http://tinyurl.com/" + shortKey;
    }

    public String decode(String shortenedUrl) {
        return urlMap.get(shortenedUrl.replace("http://tinyurl.com/", ""));
    }
}