Encode and Decode TinyUrl
Problem
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
Two HashMap Solution: O(n) time, O(n) space
public class Codec {
Map<String, String> urlMapTiny = new HashMap<>();
Map<String, String> tinyMapUrl = new HashMap<>();
final String CODES = "qwertyuiopasdfghjklzxcvbnmQWERTYUIOPASDFGHJKLZXCVBNM";
final String BASE_URL = "http://tinyurl.com/";
// Encodes a URL to a shortened URL.
public String encode(String longUrl) {
if (urlMapTiny.containsKey(longUrl)) return urlMapTiny.get(longUrl);
String tinyUrl = "";
do {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 6; i++) {
sb.append(CODES.charAt((int) Math.random() * CODES.length()));
}
tinyUrl = sb.toString();
} while (tinyMapUrl.containsKey(tinyUrl));
urlMapTiny.put(longUrl, BASE_URL + tinyUrl);
tinyMapUrl.put(tinyUrl, longUrl);
return tinyUrl;
}
// Decodes a shortened URL to its original URL.
public String decode(String shortUrl) {
return tinyMapUrl.get(shortUrl.replace(BASE_URL, ""));
}
}
Analysis
We use two hash maps to encode and decode
Notice that when we are encoding, we need to make sure the tinyUrl
is unique
We accomplish this by using do while()
loop
Inside the loop, we construct the tinyUrl by Math.random() * CODES.length()
Also notice that in decode()
we need to remove BASE_URL
cause we does not store it in our tinyUrl