⚡Flashcard Drill➔
NeetCode #106LC-535MediumArrays & Hashing
← Back to All Problems

#106 · #535 · Encode and Decode TinyURL(TinyURL 的加密与解密)

📌 Problem Statement & Constraints

Design a class that encodes a long URL into a short URL and decodes it back. There is no restriction on how the encoding works, as long as decode(encode(url)) == url. Implement encode(longUrl) and decode(shortUrl).

💡 Core Algorithmic Approaches

  1. The simplest correct design is a counter plus two hash maps: one from long URL to short URL and one in reverse.
  2. encode returns the existing short URL if the long URL was seen before, otherwise allocates the next id.
  3. decode is a single reverse-map lookup.
  4. A hash-based encoding (e.g. a digest of the URL) is a valid alternative, but then you must handle collisions and the decode map is still required.

💻 Benchmark Python3 Implementation

class Codec:
    def __init__(self):
        self.long_to_short = {}
        self.short_to_long = {}
        self.counter = 0

    def encode(self, longUrl: str) -> str:
        if longUrl not in self.long_to_short:
            self.counter += 1
            short = f"http://tinyurl.com/{self.counter}"
            self.long_to_short[longUrl] = short
            self.short_to_long[short] = longUrl
        return self.long_to_short[longUrl]

    def decode(self, shortUrl: str) -> str:
        return self.short_to_long[shortUrl]

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(1) per operation, assuming O(1) hash operations.
💾 Space Complexity
O(n) for the two maps, where n is the number of distinct URLs encoded.

⚠️ Interview Pitfalls & Follow-ups

  • Only keeping one map: you need both directions, or you would have to search the map linearly on decode.
  • Allocating a new short URL every time the same long URL is encoded: the reverse map would then contain several short URLs for one long URL, wasting space. Reuse the existing one.
  • Trying to compress the URL into the short string: the length is not what the problem measures; correctness of the round trip is.
  • Using a hash of the URL without handling collisions: two different URLs could collide, breaking decode.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Arrays & Hashing Problems