DEV Community

Cover image for Leetcode 535. Encode and Decode TinyURL [Solution and Discussion]
Shivam Sharma
Shivam Sharma

Posted on

Leetcode 535. Encode and Decode TinyURL [Solution and Discussion]

The question is very good and real-world related, but the test environment for this question in Leetcode is not up to the mark, As even below code is also accepted and it requires no effort.

class Solution {
public:
    string encode(string longUrl) {
        return longUrl;
    }
    string decode(string shortUrl) {
        return shortUrl;
    }
};
Enter fullscreen mode Exit fullscreen mode

That is happening because Leetcode is creating a new instance for each test case hence there is no need to keep past input/output in the code. Also, there are no constraints on the length of a short URL.

But we are here to learn, so ignoring such a bad test environment, we'll be creating a real-world solution. The best thing about this question is the provided hyperlink to the article.

Difficulty: Medium
Jump To:


Problem Statement

Question: https://leetcode.com/problems/encode-and-decode-tinyurl/

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.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.


Explanation

So the problem is simple, you need to create an algorithm, which will convert a long URL to a short URL and the long URL can be achieved back from the short URL. One thing to take care of is that the short URL should always map to a single long URL but vice versa is not mandatory but good to have.


Solution

There are many solutions possible to this problem, the one we are going to use is mentioned in the attached article with the question, which is "Simple Base conversion". In this method, we have a base and the base for the system is the number of distinct characters available in the system. Simplest example for it is a Decimal System which has base=10 (0-9) or a Hexadecimal Number System which has base=16 (0-9,A-D). So first let's see how we convert a decimal number to a hexadecimal number.

  1. Mod a number by Base and use the character present at this mod value.
  2. Divide the original number by base.
  3. Repeat the above steps until the number becomes zero.
  4. Now write the characters found in a reverse manner.

Eg. 1732 => 6C4

Base Number Remainder Read Direction
16 1732 4
16 108 C
16 6 6
16 0

Now again look at the problem we have a-z, A-Z and 0-9 i.e. 62 characters available to use in short URL, so we can see it as a decimal to 62-based system conversion problem. So we'll convert a number to a 62-based string and this string will be our short URL Hash. This hash can be appended to "http://tinyurl.com/" to form a complete short URL.

Wait a minute??? From where this decimal number came into the picture??? Actually, instead of converting a very long string to a short URL, we'll be converting a decimal number to a short URL and we'll bind this short URL to the long URL. Or to save space we can bind directly the decimal number to the long URL. This number is an increasing counter, which will be increased every time by 1 when encode is called.

For a limited number of long URLs, the first method is OK, but when we are going to convert billions then the second method is way better.

For the first method, In the encoding method, we require only decimal to 62-based conversion and a hash map to store pair of <Short URL Hash, Long URL>. Then in the decoding method, we'll just look up the short URL in this hash map and return the long URL.

In the Second method, we'll have a hashmap for the pair of <integer, Long URL> so we require both decimal to 62-based conversion (for encoding) and 62-based to decimal conversion (for decoding)


Implementation

C++ Code:
For method 1:

class Solution {
public:
    int counter=0;
    unordered_map<string,string> dict;

    string encode(string longUrl) {
        char cmap[] = "abcdefghijklmnopqrstuvwxyz\
            ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        int n = (++counter);
        string shortUrl;
        while(n){
            shortUrl.push_back(cmap[n%62]);
            n=n/62;
        }
        reverse(shortUrl.begin(), shortUrl.end());
        dict[shortUrl] = longUrl;
        return shortUrl;
    }

    string decode(string shortUrl) {
        return dict[shortUrl];
    }
};
Enter fullscreen mode Exit fullscreen mode

For method 2:

class Solution {
public:
    int counter=0;
    unordered_map<int,string> dict;

    string encode(string longUrl) {
        char cmap[] = "abcdefghijklmnopqrstuvwxyz\
            ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        int n = (++counter);
        string shortUrl;
        while(n){
            shortUrl.push_back(cmap[n%62]);
            n=n/62;
        }
        reverse(shortUrl.begin(), shortUrl.end());
        dict[counter] = longUrl;
        return shortUrl;
    }

    string decode(string shortUrl) {
        int id = 0; // initialize result
        for (int i=0; i < shortUrl.length(); i++)
        {
            if ('a' <= shortUrl[i] && shortUrl[i] <= 'z')
                id = id*62 + shortUrl[i] - 'a';
            if ('A' <= shortUrl[i] && shortUrl[i] <= 'Z')
                id = id*62 + shortUrl[i] - 'A' + 26;
            if ('0' <= shortUrl[i] && shortUrl[i] <= '9')
                id = id*62 + shortUrl[i] - '0' + 52;
        }
        return dict[id];
    }
};
Enter fullscreen mode Exit fullscreen mode

Runnable C++ code:

Cover Photo by Annie Spratt on Unsplash

We can have a discussion either here or here regarding this question.

Discussion (42)

Collapse
sattamarket profile image
satta matka market

I just found this blog and have high hopes for it to continue. Keep up the great work, its hard to find good ones. I have added to my favorites. Thank You. satta matka

Collapse
lnwtoonclub profile image
madtube

I've read this blog, this blog is truly educational for everyone, keep it up, thanks for participating!! We all know that for running a big sector like a power factory, real estate sector, civil sector, mechanical sector, etc. It's necessary to look for the safety of the workers. There's always a trouble of injury in the plant, that is why it's necessary to cover workers, therefore safety should betheprecedenceofanyorganisation.However, also any kind of accident can do, If the safety of the workers isn't considered. In such a situation, the government won't allow the company to operate. Safety at the plant is the first thing because the most precious thing is our life.
กลยุทธ์เด็ด เสพติดรักภรรยาของผม

Collapse
mandirbhagya profile image
Bhagya Mandir

Thanks for sharing this wonderful information. Your information is very helpful for me.
Play matka online
Play matka online
Play matka online

Collapse
lnwtoonclub profile image
madtube

A veritably stupendous blog post. We're really thankful for your blog post. You'll find a lot of approaches after visiting your post. I was exactly searching for. Thanks for similar post and please keep it up. Great work นิยายจีน pdf . นิยาย pdf

Collapse
jamesxxxd profile image
MasterX

This topic helped me a lot. thanks for your help I feel like an article like this will disappear a little bit. but i tried to find it come meet your It was absolutely wow. อ่านโดจิน

Collapse
thomashenry12312 profile image
thomashenry12312

First You got a great blog .I will be interested in 極速娛樂城 more similar topics. i see you got really very useful topics, i will be always checking your blog thanks. solo leveling

Collapse
samsimth60 profile image
samsimth60

You delivered such an impressive piece to read, 먹튀검증
giving every subject enlightenment for us to gain information. Thanks for sharing such information with us due to which my several concepts have been cleared.

Collapse
samsimth60 profile image
samsimth60 • Edited on

Thanks for picking out the time to discuss this, I feel great about it and love studying more on this topic. It is extremely helpful for me. Thanks for such a valuable help again. 토토커뮤니티

Collapse
annawalker506 profile image
anna walker

*What is 0x0 0x0 Windows Error Code? *

The very first thing that comes to mind that, what is meaning of 0x0 0x0 Windows Error Code? Well, there may be a problem with your Windows operating system in connection with a particular piece of software. By examining this code, a specialist can determine a number of things, such as what particular software is causing the issue and also what part of the system is problematic. As a result of this error code, you can deduce that the system may be experiencing problems in different areas.

Collapse
ginana profile image
Ginana

ร่วมสนุกกับ สล็อตpg ไม่มีเงินฝากขั้นต่ำผ่านช่องเว็บโดยตรง PGSLOT.BAR พร้อมให้บริการคุณตลอด 24 ชม. วันนี้รับโปรฟรี ฝาก 100 รับ 200 พิเศษ รับประกันสูงสุด 100% เว็บใหม่ เชื่อถือได้ อัตราการชนะสูงสุดของการพนันสล็อตของค่าย Slot PG

Collapse
davidjack23 profile image
David Jack

Your blog website provided us with useful information to execute with. Each & every recommendations of your website are awesome. Thanks a lot for talking about. mac optimizer

Collapse
okwebsite profile image
Masoud Sourni

We are really grateful for your blog post. You will find a lot of approaches after visiting your post.
قیمت روز آهن

Collapse
merryhere profile image
merryhere

You explained it very well. Thanks for the efforts.
anyror 7/12

Collapse
ghoomlullp profile image
fardeen siddiqui

this is our site by the way ghoomly.com

Collapse
ghoomlullp profile image
fardeen siddiqui

Love this!

We are going to use this for our company ghoomly.com

Thank you for this :)

Collapse
gosloto1 profile image
Ashwin Roy

I always use their site to get the code for my website > russia gosloto 7 49

Collapse
treableanup profile image
Treable

Are you looking for the which is the best company who are provide the corporate gift suppliers in Mumbai then visit our company website Bigimpex are best one

Collapse
davidjack23 profile image
David Jack

ruly appreciate this article.Really looking forward to read more. Great. PC Optimizer

Collapse
samsimth60 profile image
samsimth60

I really appreciate this wonderful post that you have provided for us. I assure this would be beneficial for most of the people.
먹튀검증