March-leetcoding-challenge-2021 : Encode and Decode TinyURL — step by step

Problem statement

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.

Solution

public class Codec {

Map<String, String> longToShort = new HashMap<>();
Map<String, String> shortToLong = new HashMap<>();

String tinyUrlBase = “http://tinyurl.com/";
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
if(longToShort.containsKey(longUrl))
return longToShort.get(longUrl);
String index = longUrl.hashCode();
String shortUrl = tinyUrlBase + index;
longToShort.put(longUrl, shortUrl);
shortToLong.put(shortUrl, longUrl);

return shortUrl;
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
return shortToLong.get(shortUrl);
}
}

739 / 739 test cases passed.

Status: Accepted

Runtime: 7 ms

Memory Usage: 39 MB

Hashcode can result in collisions, even if two longUrl are not ‘equal’. So, let’s replace it with maintaining all longUrls in map and assign a counter to these entries.

public class Codec {

Long counter = 1L;
Map<Long, String> indexToUrl = new HashMap<>(); //id corresponding to long url
Map<String, Long> urlToIndex = new HashMap<>(); //long url corresponding to id
String tinyUrlBase = “http://tinyurl.com/”;
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
if(!urlToIndex.containsKey(longUrl)){
indexToUrl.put(counter, longUrl);
urlToIndex.put(longUrl, counter);
counter++;
}
return tinyUrlBase + urlToIndex.get(longUrl);
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
String count = shortUrl.replace(tinyUrlBase,””);
return indexToUrl.get(Long.parseLong(count));
}
}

739 / 739 test cases passed.

Status: Accepted

Runtime: 5 ms

Memory Usage: 39.2 MB

Please refer to my article at https://bit.ly/3rakXsw to understand why to choose Base64 encoding in detail.

public class Codec {

...
String base62 = “0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ”;
...
public String encode(String longUrl) {
if(!urlToIndex.containsKey(longUrl)){
indexToUrl.put(counter, longUrl);
urlToIndex.put(longUrl, counter);
counter++;
}
return tinyUrlBase + base62Encode(urlToIndex.get(longUrl));
}
public String decode(String shortUrl) {
String base62Encoded = shortUrl.substring(shortUrl.lastIndexOf(“/”)+1);

long decode=0;
for(int i=0;i<base62Encoded.length();i++){
decode = decode*62 + base62.indexOf(base62Encoded.charAt(i));
}
return indexToUrl.get(decode);
}

String base62Encode(long value){
StringBuffer sb = new StringBuffer();
while(value>0){
sb.append(base62.charAt((int)(value%62)));
value=value/62;
}
//to make it 7 char
while(sb.length()<7){
sb.append(0);
}
return sb.reverse().toString();
}
}

739 / 739 test cases passed.

Status: Accepted

Runtime: 4 ms

Memory Usage: 39.3 MB

Hence, by alloting same space and faster runtime, we can make out Url-Shortner more scalable.

To provide a stateless API to generate tiny url, and retreive the same using short Url, replace the Map and counter used in previous code with a database connection.

Saving longUrl to database, will generate a unique ID (as counter), which can be converted to Base62Encoded value and appended to base url to get a unique and scalable shortUrl.

I hope this article helps you to understand how to code step by step for designing a Url Shortner. Please do let me know if you have any questions. If you like the post, do share some claps :)

Developer, melomaniac, philospher, tea lover