LeetCode 535: Encode and Decode TinyURL Solution in Python – A Step-by-Step Guide

What Is LeetCode 535: Encode and Decode TinyURL?

In LeetCode 535: Encode and Decode TinyURL, you’re tasked with designing a Codec class 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 must be unique, shorter than the original, and correctly map back to the long URL. For example, encoding "https://leetcode.com/problems/design-tinyurl" might yield "tinyurl.com/abc123," and decoding that returns the original. This problem tests hash map usage and string manipulation, related to LeetCode 146: LRU Cache for key-value storage.

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://leetcode.com/problems/design-tinyurl"],["tinyurl.com/abc123"]] ```
• Output:
``` ["tinyurl.com/abc123","https://leetcode.com/problems/design-tinyurl"] ```
• Input:
``` ["encode","encode","decode"] [["https://www.example.com"],["https://python.org"],["tinyurl.com/xyz789"]] ```
• Output:
``` ["tinyurl.com/xyz789","tinyurl.com/pqr456","https://www.example.com"] ```

Understanding the Problem: Shortening URLs

To solve LeetCode 535: Encode and Decode 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 store the full URL as a key, but we need short, unique codes. With up to 10⁴ calls, efficiency and simplicity are key. We’ll explore:

• Best Solution (Hash Map with Random Key Generation): O(1) average encode/decode, O(n) space (n = URLs)—simple and fast.
• Alternative Solution (Base62 Encoding with Counter): O(1) encode/decode, O(n) space—predictable but requires base conversion.

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

Best Solution: Hash Map with Random Key Generation

Why Random Key Generation Wins

The hash map with random key generation is the best for LeetCode 535 because it’s straightforward, generates short unique codes in O(1) average time per operation using a random 6-character key, and uses O(n) space with a hash map for storage. It’s like rolling a dice to pick a short code and checking if it’s taken!

How It Works

Think of this as a URL lottery:

• Step 1: Setup:
• Use a hash map to store short-to-long URL mappings.
• Define an alphabet (e.g., a-z, A-Z, 0-9) for random keys.
• Step 2: Encode:
• Generate a random 6-character key (e.g., "xyz123").
• If key exists, retry until unique.
• Form short URL (e.g., "tinyurl.com/xyz123"), store in map.
• Step 3: Decode:
• Extract key from short URL, look up in map.
• Why It Works:
• 6 chars with 62 options ≈ 56 million possibilities, low collision chance for 10⁴ URLs.
• Simple and fast with hash map lookups.

It’s like a TinyURL dice roller!

Step-by-Step Example

Example: Encoding "https://leetcode.com/problems/design-tinyurl"

• Init: url_map = {}, chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789".
• Step 1: encode("https://leetcode.com/problems/design-tinyurl"):
• Random key = "abc123".
• Short URL = "tinyurl.com/abc123".
• url_map["abc123"] = "https://leetcode.com/problems/design-tinyurl".
• Step 2: encode("https://www.example.com"):
• Random key = "xyz789" (assume "abc123" not reused).
• Short URL = "tinyurl.com/xyz789".
• url_map["xyz789"] = "https://www.example.com".
• Step 3: decode("tinyurl.com/abc123"):
• Extract "abc123", url_map["abc123"] = "https://leetcode.com/problems/design-tinyurl".
• Result: "https://leetcode.com/problems/design-tinyurl".

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

Copy codeimport random

class Codec:
    def __init__(self):
        # Step 1: Initialize hash map and alphabet
        self.url_map = {}
        self.chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        self.prefix = "tinyurl.com/"

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

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

• Lines 6-8: Constructor: Hash map, 62-char alphabet, prefix.
• Lines 11-16: encode:
• Generate 6-char key, ensure uniqueness, store mapping.
• Lines 19-21: decode:
• Extract key, return long URL.
• Time Complexity: O(1) average—rare collisions.
• Space Complexity: O(n)—hash map size.

It’s like a TinyURL randomizer!

Alternative Solution: Base62 Encoding with Counter

Why an Alternative Approach?

The base62 encoding with counter solution uses a counter to generate deterministic short codes, converting them to base62 (a-z, A-Z, 0-9), ensuring uniqueness without retries. It’s O(1) time per operation (base conversion is small) and O(n) space—predictable but requires base62 logic. Great for deterministic fans!

How It Works

Picture this as a URL code counter:

• Step 1: Setup hash map, counter, base62 alphabet.
• Step 2: encode:
• Increment counter, convert to base62 (e.g., 1 → "a").
• Form short URL, store in map.
• Step 3: decode:
• Extract code, lookup in map.

It’s like a TinyURL counter!

Step-by-Step Example

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

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

Code for Base62 Approach

Copy codeclass Codec:
    def __init__(self):
        self.url_map = {}
        self.counter = 0
        self.base62 = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
        self.prefix = "tinyurl.com/"

    def encode(self, longUrl: str) -> str:
        self.counter += 1
        num = self.counter
        code = ""
        while num > 0:
            code = self.base62[num % 62] + code
            num //= 62
        short_url = self.prefix + code
        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)—base62 conversion is small.
• Space Complexity: O(n)—hash map.

It’s a base62 URL encoder!

Comparing the Two Solutions

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

Random key wins for simplicity!

Additional Examples and Edge Cases

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

Random key handles them all!

Complexity Recap

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

Random key’s the simplicity champ!

Key Takeaways

• Random Key: Easy wins—learn at Python Basics!
• Base62: Predictable power.
• Design: URLs are fun.
• Python: Random or counters, your pick!

Final Thoughts: Shrink Those Links!

LeetCode 535: Encode and Decode TinyURL in Python is a creative design challenge. Hash map with random keys is your fast track, while base62 offers a deterministic twist. Want more? Try LeetCode 146: LRU Cache or LeetCode 208: Implement Trie. Ready to encode? Head to Solve LeetCode 535 on LeetCode and shorten those URLs today!