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
- The simplest correct design is a counter plus two hash maps: one from long URL to short URL and one in reverse.
encodereturns the existing short URL if the long URL was seen before, otherwise allocates the next id.decodeis a single reverse-map lookup.- 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.