Leetcode 535. Encode and Decode TinyURL [Solution and Discussion]
Tags: algorithms, programming, cpp, tutorial
Published: 2021-03-15 13:19:24

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. 
```cpp
class Solution {
public:
    string encode(string longUrl) {
        return longUrl;
    }
    string decode(string shortUrl) {
        return shortUrl;
    }
};
```
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](https://leetcode.com/discuss/interview-question/124658/Design-a-URL-Shortener-%28-TinyURL-%29-System/) to the article.

**Difficulty:** Medium
**Jump To:**
* [Problem Statement](#problem-statement)
* [Explanation](#explanation)
* [Solution](#solution)
* [Implementation](#implementation)

---

## Problem Statement <a name="problem-statement"></a>

**Question:** [https://leetcode.com/problems/encode-and-decode-tinyurl/](https://leetcode.com/problems/encode-and-decode-tinyurl/)


> Note: This is a companion problem to the  [System Design](https://leetcode.com/discuss/interview-question/system-design/)  problem:  [Design TinyURL](https://leetcode.com/discuss/interview-question/124658/Design-a-URL-Shortener-(-TinyURL-)-System/).

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 <a name="explanation"></a>

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 <a name="solution"></a>

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](https://en.wikipedia.org/wiki/Hexadecimal#Division-remainder_in_source_base).
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 <a name="implementation"></a>

**C++ Code:**
For method 1:

```cpp
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];
	}
};
```

For method 2:

```cpp
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];
	}
};
```


**Runnable C++ code:**

{% replit @shivams136/Leetcode-535-Encode-and-Decode-TinyURL %}

Cover Photo by [Annie Spratt](https://unsplash.com/@anniespratt?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText) on [Unsplash](/s/photos/tiny-text?utm_source=unsplash&utm_medium=referral&utm_content=creditCopyText)

We can have a discussion either here or [here](https://leetcode.com/problems/encode-and-decode-tinyurl/discuss/1110712/The-question-is-good-but-very-bad-testbed-I-am-disappointed) regarding this question.