Encode and Decode TinyURL

LeetCode 535 | Difficulty: Medium

Medium

Problem 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 a class to encode a URL and decode a tiny URL.

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.

Implement the Solution class:

- `Solution()` Initializes the object of the system.

- `String encode(String longUrl)` Returns a tiny URL for the given `longUrl`.

- `String decode(String shortUrl)` Returns the original long URL for the given `shortUrl`. It is guaranteed that the given `shortUrl` was encoded by the same object.

Example 1:

Input: url = "https://leetcode.com/problems/design-tinyurl"
Output: "https://leetcode.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 <= 10^4`

- `url` is guranteed to be a valid URL.

Topics: Hash Table, String, Design, Hash Function

---

Approach

Hash Map

Use a hash map for O(1) average lookups. Store seen values, frequencies, or indices. The key question: what should I store as key, and what as value?

When to use

Need fast lookups, counting frequencies, finding complements/pairs.

Design

Choose the right data structures to meet the required time complexities for each operation. Consider hash maps for O(1) access, doubly-linked lists for O(1) insertion/deletion, and combining structures for complex requirements.

When to use

Implementing a data structure or system with specific operation time requirements.

String Processing

Consider character frequency counts, two-pointer approaches, or building strings efficiently. For pattern matching, think about KMP or rolling hash. For palindromes, expand from center or use DP.

When to use

Anagram detection, palindrome checking, string transformation, pattern matching.

---

Solutions

Solution 1: C# (Best: 84 ms)

Metric	Value
Runtime	84 ms
Memory	40.3 MB
Date	2022-02-04

Solution

public class Codec {

    private Dictionary<string, string> longtoShort = new Dictionary<string, string>();
    private Dictionary<string, string> shortToLong = new Dictionary<string, string>();
    private const string base62 = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    private int counter = 0;
    private const string baseUrl = @"http://tinyurl.com/";  
    
    // Encodes a URL to a shortened URL
    public string encode(string longUrl)
    {
        if(longtoShort.ContainsKey(longUrl)) return longtoShort[longUrl];
        string shortUrl = baseUrl + GetShortString(longUrl);
        longtoShort.Add(longUrl, shortUrl);
        shortToLong.Add(shortUrl, longUrl);
        return shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    public string decode(string shortUrl)
    {
        return shortToLong[shortUrl];
    }
    
    private string GetShortString(string longUrl)
    {
        int n = counter++;
        StringBuilder sb = new StringBuilder();
        while(n>0)
        {
            sb.Append(base62[n%62]);
            n = n/62;
        }
        return sb.ToString();
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

📜 1 more C# submission(s)

Submission (2022-02-04) — 137 ms, 37.8 MB

public class Codec {

    // Encodes a URL to a shortened URL
    public string encode(string longUrl) {
        return longUrl;
    }

    // Decodes a shortened URL to its original URL.
    public string decode(string shortUrl) {
        return shortUrl;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

---

Complexity Analysis

Approach	Time	Space
Hash Map	$O(n)$	$O(n)$

---

Interview Tips

Key Points

• Discuss the brute force approach first, then optimize. Explain your thought process.
• Hash map gives O(1) lookup — think about what to use as key vs value.
• Clarify the expected time complexity for each operation before choosing data structures.