TinyURL is a URL shortening service where you enter a URL such as https://cscode.io/algo/strings/EncodeDecodeTinyURL
and it returns a short URL such as http://tinyurl.com/4e9iAk. Design a class to encode a URL and decode a tiny URL.
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.
Implement the Solution class:
-
Solution() Initializes the object of the system.
-
String encode(String longUrl) Returns a tiny URL for the given longUrl.
-
String decode(String shortUrl) Returns the original long URL for the given shortUrl. It is guaranteed that the given shortUrl was encoded by the same object.
Input: url = "https://cscode.io/algo/strings/EncodeDecodeTinyURL"
Output: "https://cscode.io/algo/strings/EncodeDecodeTinyURL"
Explanation: After encoding, decoding should return the same value back.
Contents
- Solution 1 - Using number digits to encode the URL
In this approach, we are going to encode just using number digits 0 to 9. With this combination of number digits,
we will get 0 to 9999999999 number of unique combinations if we can assume that we want to get a 10 character lenght encoded string
(1010 ),
but if you want you can add alphabets (both uppercase and lowercase) to get even more unique combinations and you will get 6210 unique combinations.
Implementation details:
-
We will two HashMaps to store mappings, one map encodedMap to store mapping from encoded long url to tiny url
and another map decodedMap to store mapping from tiny url to long url.
-
In encode function, we will simply encode using encodedMap.size() +1 and store this mapping into both maps.
-
In decode function, we will return the value from decodedMap.
import java.util.HashMap;
import java.util.Objects;
public class EncodeDecodeTinyURL {
static String tinyURL = "http://tinyurl.com/";
static final HashMap>String, String> encodedMap = new HashMap>>();
static final HashMap>String, String> decodedMap = new HashMap>>();
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
String alreadyExists = encodedMap.get(longUrl);
if(!Objects.isNull(alreadyExists)) { // if the longUrl is already encoded, then return that
return alreadyExists;
}
String encodedURL = tinyURL + (encodedMap.size()+1);
encodedMap.put(longUrl, encodedURL);
decodedMap.put(encodedURL, longUrl);
return encodedURL;
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
return decodedMap.get(shortUrl);
}
public static void main(String[] args) {
String longUrl = "https://cscode.io/algo/strings/EncodeDecodeTinyURL/";
String encoded = new EncodeDecodeTinyURL().encode(longUrl);
String decoded = new EncodeDecodeTinyURL().decode(encoded);
System.out.println("Encoded : " +encoded +" , Decoded : "+decoded);
assert longUrl.equals(decoded);
}
}
Complexity Analysis:
Time complexity: Above code runs in O(1) time since we are just storing the mappings into HashMap and the lookups take constant time.
Space complexity: O(n * m) where n is the total number of long URL's this application may get to encode
and m is the average length of a long URL.
Above implementations source code can be found at
GitHub link for Java code