LeetCode 534: Design TinyURL Solution in Python – A Step-by-Step Guide

What Is LeetCode 534: Design TinyURL?

In LeetCode 534: Design TinyURL, you’re tasked with designing a system with two methods: encode(longUrl) to convert a long URL into a short one, and decode(shortUrl) to retrieve the original URL. The short URL should be unique, shorter than the original, and map back correctly. For example, encoding "https://www.example.com" might yield "tinyurl.com/ab12cd", and decoding that returns the original. This problem tests data structure design, related to LeetCode 535: Encode and Decode TinyURL.

Problem Statement

• Input:
• encode(longUrl): String—original URL.
• decode(shortUrl): String—shortened URL.
• Output:
• encode: String—short URL.
• decode: String—original URL.
• Rules: Short URL must be unique, shorter than original; decode must return exact input.

Constraints

• 1 <= longUrl.length <= 10⁴
• URLs are valid and contain lowercase letters, digits, and special characters.
• At most 10⁴ calls to encode and decode.

Examples

• Input:
``` ["encode","decode"] [["https://www.example.com"], ["tinyurl.com/ab12cd"]] ```
• Output:
``` ["tinyurl.com/ab12cd", "https://www.example.com"] ```
• Input:
``` ["encode","encode","decode"] [["https://leetcode.com"],["https://python.org"],["tinyurl.com/xy34ab"]] ```
• Output:
``` ["tinyurl.com/xy34ab","tinyurl.com/pq56cd","https://leetcode.com"] ```

Understanding the Problem: Shortening URLs

To solve LeetCode 534: Design TinyURL in Python, we need a class with encode and decode methods that map long URLs to unique short URLs and back. A naive approach might use the long URL as a key, but we need short, unique codes. With up to 10⁴ calls, we can design an efficient system. We’ll explore:

• Best Solution (Hash Map with Base62 Encoding): O(1) encode/decode, O(n) space (n = URLs)—efficient and scalable.
• Alternative Solution (Random Key Generation with Hash Map): O(1) average encode/decode, O(n) space—simple but probabilistic.

Let’s dive into the base62 solution with a friendly breakdown!

Best Solution: Hash Map with Base62 Encoding

Why Base62 Encoding Wins

The hash map with base62 encoding is the best for LeetCode 534 because it generates short, unique codes deterministically using a base62 alphabet (a-z, A-Z, 0-9), mapping them to long URLs in a hash map, with O(1) time for both operations and O(n) space. It’s like turning a counter into a compact, readable code!

How It Works

Think of this as a URL code generator:

• Step 1: Setup:
• Use a hash map to store short-to-long URL mappings.
• Define base62 alphabet (62 characters).
• Step 2: Encode:
• Increment a counter, convert to base62 (e.g., 1 → "a", 62 → "ba").
• Form short URL (e.g., "tinyurl.com/" + code).
• Store in map.
• Step 3: Decode:
• Extract code from short URL, look up in map.
• Why It Works:
• Base62 keeps codes short (6 chars ≈ 568 million possibilities).
• Deterministic, no collisions.

It’s like a URL shortening wizard!

Step-by-Step Example

Example: Encoding "https://www.example.com"

• Init: counter = 0, map = {}, base62 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".
• Step 1: encode("https://www.example.com"):
• counter = 1, base62: 1 → "b" (index 1).
• Short URL = "tinyurl.com/b".
• map["b"] = "https://www.example.com".
• Step 2: encode("https://leetcode.com"):
• counter = 2, base62: 2 → "c".
• Short URL = "tinyurl.com/c".
• map["c"] = "https://leetcode.com".
• Step 3: decode("tinyurl.com/b"):
• Extract "b", map["b"] = "https://www.example.com".
• Result: "https://www.example.com".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeclass Solution:
    def __init__(self):
        # Step 1: Initialize hash map, counter, and base62 alphabet
        self.url_map = {}
        self.counter = 0
        self.base62 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        self.prefix = "tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        # Step 2: Generate base62 code from counter
        self.counter += 1
        code = ""
        num = self.counter
        while num > 0:
            code = self.base62[num % 62] + code
            num //= 62

        # Form short URL and store
        short_url = self.prefix + code
        self.url_map[code] = longUrl
        return short_url

    def decode(self, shortUrl: str) -> str:
        # Step 3: Extract code and lookup
        code = shortUrl[len(self.prefix):]
        return self.url_map.get(code, "")

• Lines 4-7: Constructor: Hash map, counter, base62 alphabet, prefix.
• Lines 10-16: encode:
• Increment counter, convert to base62.
• Lines 18-19: Form short URL, store mapping.
• Lines 22-24: decode:
• Extract code, return long URL.
• Time Complexity: O(1) encode/decode (base62 conversion is O(log n) but small).
• Space Complexity: O(n)—hash map size.

It’s like a TinyURL encoder!

Alternative Solution: Random Key Generation with Hash Map

Why an Alternative Approach?

The random key generation with hash map generates random 6-character keys using a smaller alphabet (e.g., a-z), checking for uniqueness, with O(1) average time per operation and O(n) space. It’s simple but probabilistic, risking collisions. Great for randomness fans!

How It Works

Picture this as a URL lottery:

• Step 1: Setup hash map and alphabet (e.g., a-z).
• Step 2: encode:
• Generate random 6-char key, retry if taken.
• Store in map with long URL.
• Step 3: decode:
• Extract key, lookup in map.

It’s like a random URL shortener!

Step-by-Step Example

Example: Encoding "https://www.example.com"

• Init: map = {}, chars = "abcdefghijklmnopqrstuvwxyz".
• Step 1: encode:
• Random key = "xyzabc".
• Short URL = "tinyurl.com/xyzabc".
• map["xyzabc"] = "https://www.example.com".
• Step 2: decode("tinyurl.com/xyzabc"):
• Key = "xyzabc", map["xyzabc"] = "https://www.example.com".
• Result: "https://www.example.com".

Code for Random Key Approach

Copy codeimport random

class Solution:
    def __init__(self):
        self.url_map = {}
        self.chars = "abcdefghijklmnopqrstuvwxyz"
        self.prefix = "tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        while True:
            code = ''.join(random.choice(self.chars) for _ in range(6))
            short_url = self.prefix + code
            if code not in self.url_map:
                self.url_map[code] = longUrl
                return short_url

    def decode(self, shortUrl: str) -> str:
        code = shortUrl[len(self.prefix):]
        return self.url_map.get(code, "")

• Time Complexity: O(1) average—rare collisions.
• Space Complexity: O(n)—hash map.

It’s a random URL shrinker!

Comparing the Two Solutions

• Base62 Encoding (Best):
• Pros: O(1), O(n), deterministic.
• Cons: Base62 conversion logic.
• Random Key (Alternative):
• Pros: O(1) avg, O(n), simple.
• Cons: Collision risk.

Base62 wins for predictability!

Additional Examples and Edge Cases

• "https://a.com": Shortens uniquely.
• Duplicate URLs: Same short URL (allowed).
• Long URLs: Consistent shortening.

Base62 handles them all!

Complexity Recap

• Base62: Init O(1), Encode/Decode O(1), Space O(n).
• Random Key: Init O(1), Encode/Decode O(1) avg, Space O(n).

Base62’s the efficiency champ!

Key Takeaways

• Base62: Compact codes—learn at Python Basics!
• Random: Easy but risky.
• Design: URLs are fun.
• Python: Dicts rule!

Final Thoughts: Shrink Those URLs!

LeetCode 534: Design TinyURL in Python is a creative design challenge. Base62 encoding with hash map is your fast track, while random keys offer a simple twist. Want more? Try LeetCode 535: Encode and Decode TinyURL or LeetCode 146: LRU Cache. Ready to shorten? Head to Solve LeetCode 534 on LeetCode and design that TinyURL today!