MediumNo. 0535

Encode and Decode TinyURL — LeetCode 535 Python Solution

Pattern
Hash Map
Topics
Design, Hash Table, String, Hash Function
Reading time
4 min

The problem

Note: This is a companion problem to the System Design problem: Design TinyURL. TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Example

Input
url = "https://leetcode.com/problems/design-tinyurl"
Output
"https://leetcode.com/problems/design-tinyurl"
Explanation
Solution obj = new Solution();

Python solution

PythonSolution
class Codec:
    def __init__(self):
        self.m = defaultdict()
        self.idx = 0
        self.domain = 'https://tinyurl.com/'

    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL."""
        self.idx += 1
        self.m[str(self.idx)] = longUrl
        return f'{self.domain}{self.idx}'

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL."""
        idx = shortUrl.split('/')[-1]
        return self.m[idx]


# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))

Complexity

Time
O(n)
Space · auxiliary
O(n)

Pattern: Hash Map

Trade memory for time: remember what you have seen so the second pass never happens. LeetCode 535. Encode and Decode TinyURL is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Hash Table.

The hash map guide has the Python template for the pattern and the 709 LeetCode problems that use it.

Related problems

Related problems
No.ProblemDifficulty
0187Repeated DNA SequencesMedium
0208Implement Trie (Prefix Tree)Medium
0676Implement Magic DictionaryMedium
0677Map Sum PairsMedium
0705Design HashSetEasy
0706Design HashMapEasy

Frequently asked questions

How hard is LeetCode 535. Encode and Decode TinyURL?

LeetCode 535. Encode and Decode TinyURL is rated Medium on LeetCode.

What is the time complexity of LeetCode 535. Encode and Decode TinyURL?

The Python solution on this page runs in O(n).

What is the space complexity of LeetCode 535. Encode and Decode TinyURL?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 535. Encode and Decode TinyURL cover?

LeetCode 535. Encode and Decode TinyURL is tagged Design, Hash Table, String and Hash Function on LeetCode.

Stuck on problems like this in a live interview?

Stealth Interview is a desktop app for macOS and Windows. It reads the problem off your screen and returns a working solution with a step-by-step explanation and its time and space complexity, invisible to screen sharing.

Free to download. Check it runs on your machine, then pick a plan.