algoadvance

Leetcode 535. Encode and Decode TinyURL

Problem Statement

Design a URL shortening service like TinyURL. Design two functions:

  1. string encode(string longUrl) - Encodes a URL to a shortened URL.
  2. string decode(string shortUrl) - Decodes a shortened URL to its original URL.

Clarifying Questions

  1. Q: Is there a specific character limit for the shortened URL? A: Let’s assume typical constraints with a reasonably short length, commonly using a base62 encoding (characters a-z, A-Z, 0-9).

  2. Q: Will the service need to handle very large numbers of URLs efficiently? A: Assume yes, so the solution should consider efficient storage and retrieval.

  3. Q: Are there any constraints on the characters in the URLs? A: Assume URLs follow standard formatting without special constraints, typically alphanumeric and common punctuation.

  4. Q: Does the service have to be stateless? A: No, it’s okay to use some form of storage for mappings between original and shortened URLs.

With these questions clarified, let’s proceed to the strategy and implementation.

Strategy

  1. Data Storage:
    • Use a hash map (or unordered_map in C++) to map the shortened URL code to the original URL.
    • Implement a counter to generate unique codes for each URL.
  2. Encoding:
    • Generate a unique ID for each long URL.
    • Convert the ID to a base62 string to create a short URL.
  3. Decoding:
    • Simply map the short URL back to the original using the stored mappings.
  4. Components:
    • A map to store the encoded URL mappings.
    • A method to convert a number to a base62 string.

Code

#include <iostream>
#include <unordered_map>
#include <string>

class Solution {
private:
    std::unordered_map<std::string, std::string> urlMap;
    int counter;
    std::string base62chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";

    std::string idToShortURL(int n) {
        std::string shortURL;
        while (n > 0) {
            shortURL += base62chars[n % 62];
            n = n / 62;
        }
        reverse(shortURL.begin(), shortURL.end());
        return shortURL;
    }

    int shortURLToID(const std::string& shortURL) {
        int id = 0;
        for (char c : shortURL) {
            if ('a' <= c && c <= 'z') id = id * 62 + c - 'a';
            if ('A' <= c && c <= 'Z') id = id * 62 + c - 'A' + 26;
            if ('0' <= c && c <= '9') id = id * 62 + c - '0' + 52;
        }
        return id;
    }

public:
    Solution() : counter(1) {}

    std::string encode(const std::string& longUrl) {
        std::string shortURL = idToShortURL(counter);
        urlMap[shortURL] = longUrl;
        ++counter;
        return "http://tinyurl.com/" + shortURL;
    }

    std::string decode(const std::string& shortUrl) {
        std::string shortKey = shortUrl.substr(shortUrl.find_last_of('/') + 1); 
        return urlMap[shortKey];
    }
};

int main() {
    Solution tinyUrlService;
    std::string url = "https://www.example.com";
    std::string shortUrl = tinyUrlService.encode(url);
    std::cout << "Short URL: " << shortUrl << std::endl;
    std::cout << "Original URL: " << tinyUrlService.decode(shortUrl) << std::endl;

    return 0;
}

Time Complexity

The time complexity for encoding and decoding operations is as follows:

Space Complexity

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI