Abstract / Summary

Design a system to convert long urls into short ones and retrieve the original from the short version.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 87% (300k+ submissions).

Typical patterns to solve this problem:

• Design
• Hash Function
• Hash Table
• String

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided module implements a simple URL shortening service through a Codec class. Two public methods, encode and decode, transform a long URL into a shortened representation and retrieve the original URL from that representation, respectively. Internally the class maintains a dictionary that maps each generated short URL to its corresponding long URL, enabling constant-time lookups.

Encoding Logic

The encode method receives a string containing the original URL. It first computes a hash value of the input, applies abs to guarantee a non-negative integer, and then concatenates this numeric identifier to a fixed domain prefix. The resulting string forms the short URL. The method prints the short URL (useful for debugging or interactive sessions) and stores the mapping in the class-level dictionary before returning the short URL.

def encode(self, longUrl: str) -> str:
    shortUrl = "https://tinyurl.com/" + str(abs(hash(longUrl)))
    print(shortUrl)
    self.urls[shortUrl] = longUrl
    return shortUrl

Key aspects of this step include:

• Use of Python’s built-in hash function to derive a deterministic identifier from the input URL.
• Application of abs to avoid a leading minus sign, ensuring the short URL remains a valid path component.
• Direct string concatenation, which is efficient for short strings.
• Immediate insertion of the mapping into self.urls, guaranteeing that a subsequent decode operation can locate the original URL without additional computation.

Decoding Logic

The decode method accepts a short URL string and retrieves the original long URL by performing a dictionary lookup using the short URL as the key. The method returns the stored long URL directly.

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

Because the dictionary provides average-case constant-time access, the decode operation is fast regardless of the number of stored URLs.

Edge Cases Handled

When the same long URL is encoded multiple times, the hash function yields the same integer, resulting in an identical short URL. The implementation therefore naturally deduplicates repeated encodings without extra logic; the dictionary entry is simply overwritten with the same value.

The use of abs ensures that URLs whose hash value is negative still produce a syntactically correct short URL, avoiding characters that could interfere with URL parsing.

If a short URL that was never generated by encode is supplied to decode, the dictionary lookup will raise a KeyError. This behavior signals that the caller attempted to decode an unknown identifier, which aligns with typical expectations for a lookup failure.

Performance Considerations

The class stores mappings in a plain Python dictionary, which offers average-case constant-time performance for both insertion (during encoding) and retrieval (during decoding). This choice eliminates the need for linear scans or more complex data structures.

Generating the short URL relies on the built-in hash function, which is highly optimized in CPython and runs in constant time relative to the length of the input string. By converting the hash to a string only once and concatenating it with a static prefix, the method avoids repeated allocations.

Printing the short URL introduces a minimal I/O overhead, but because it occurs only once per encoding call, it does not dominate the overall runtime.

Overall, the design leverages Python’s native data structures and hashing capabilities to keep both encoding and decoding operations lightweight and scalable for a large number of URLs.

Imagine a magic notebook that helps turn long, wiggly sentences into tiny labels. The class is like a big toy box where all these labels are kept safe.

When a long address needs to be hidden, the computer gives it a special number and puts a short label on it. This label is like a secret code that is much easier to carry around. The computer writes down the secret code and the long address next to each other in the notebook so it does not forget what matches.

Later, if anyone brings the secret code back to the box, the computer looks at the notebook to see which long address belongs to that code. It reads the notebook to find the secret match and brings back the original long address just like it was before.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

not analyzed yet

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java				Python		TS
	WalkCCC	C++	Java				Python
	leetcode.ca	C++	Java				Python	Go
	LeetcodeHelp	C++	Java				Python
	Progiez	C++	Java				Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	DimitrisJim			JS
	fartem					Ruby
	fengvyi	C++
	gouthampradhan		Java
	halfrost							Go
	JoshCrozier			JS
	keineahnung2345	C++
	Krazune	C++
	linouk23	C++
	sonugiri1043	C++
	suxrobGM				C#
	varunu28		Java
	wisdompeak	C++
	YuriSpiridonov						Python
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	JavaScript
fartem	Ruby
fengvyi	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
keineahnung2345	C++
Krazune	C++
linouk23	C++
sonugiri1043	C++
suxrobGM	C#
varunu28	Java
wisdompeak	C++
YuriSpiridonov	Python
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality