Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/535.html
535. Encode and Decode TinyURL
Level
Medium
Description
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.
Solution
Use a map to store each encoded short URL and the corresponding long URL before encoding. Maintain a counter count
that represents the number of URLs that have been encoded, which is initially 0.
Each time encode
is called, increase count
by 1, and create the short URL as "http://tinyurl.com/" + count
. Map the short URL to the original long URL, and the key-value pair (the key is the short URL and the value is the long URL) is stored in the map.
Each time decode
is called, simply obtain the long URL from the map using the short URL as the key.
-
public class Encode_and_Decode_TinyURL { class Codec { private static final String BASE_HOST = "http://tinyurl.com/"; private static final String SEED = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; // maintain 2 mapping relationships, could be in memory or database or disk file private Map<String, String> keyToUrl = new HashMap<>(); private Map<String, String> urlToKey = new HashMap<>(); // Encodes a URL to a shortened URL. public String encode(String longUrl) { if (urlToKey.containsKey(longUrl)) { // could also be collision and hash to different tinyUrl return BASE_HOST + urlToKey.get(longUrl); } String key = null; do { StringBuilder sb = new StringBuilder(); for (int i = 0; i < 6; i++) { int r = (int)(Math.random() * SEED.length()); sb.append(SEED.charAt(r)); } key = sb.toString(); } while (keyToUrl.containsKey(key)); keyToUrl.put(key, longUrl); urlToKey.put(longUrl, key); return BASE_HOST + key; } // Decodes a shortened URL to its original URL. public String decode(String shortUrl) { return keyToUrl.get(shortUrl.replace(BASE_HOST, "")); } } } ############ public class Codec { private Map<String, String> m = new HashMap<>(); private int idx = 0; private String domain = "https://tinyurl.com/"; // Encodes a URL to a shortened URL. public String encode(String longUrl) { String v = String.valueOf(++idx); m.put(v, longUrl); return domain + v; } // Decodes a shortened URL to its original URL. public String decode(String shortUrl) { int i = shortUrl.lastIndexOf('/') + 1; return m.get(shortUrl.substring(i)); } } // Your Codec object will be instantiated and called as such: // Codec codec = new Codec(); // codec.decode(codec.encode(url));
-
class Codec: def __init__(self): self.m = defaultdict() self.idx = 0 self.domain = 'https://tinyurl.com/' def encode(self, longUrl: str) -> str: """Encodes a URL to a shortened URL.""" self.idx += 1 self.m[str(self.idx)] = longUrl return f'{self.domain}{self.idx}' def decode(self, shortUrl: str) -> str: """Decodes a shortened URL to its original URL.""" idx = shortUrl.split('/')[-1] return self.m[idx] # Your Codec object will be instantiated and called as such: # codec = Codec() # codec.decode(codec.encode(url)) ############ class Codec: BASE = 62 UPPERCASE_OFFSET = 55 LOWERCASE_OFFSET = 61 DIGIT_OFFSET = 48 num_sender = 0 url = {} def encode(self, longUrl): """Encodes a URL to a shortened URL. :type longUrl: str :rtype: str """ if Codec.num_sender == 0: Codec.url[Codec.num_sender] = longUrl return '0' s_url = '' while Codec.num_sender > 0: tail = Codec.num_sender % Codec.BASE s_url = self.parse_chr(tail) + s_url Codec.num_sender //= Codec.BASE Codec.url[Codec.num_sender] = longUrl Codec.num_sender += 1 return s_url def decode(self, shortUrl): """Decodes a shortened URL to its original URL. :type shortUrl: str :rtype: str """ num = 0 for i, char in enumerate(reversed(shortUrl)): num += self.parse_ord(char) * (Codec.BASE**i) return Codec.url[num] def parse_ord(self, char): if char.isdigit(): return ord(char) - Codec.DIGIT_OFFSET elif char.islower(): return ord(char) - Codec.LOWERCASE_OFFSET elif char.isupper(): return ord(char) - Codec.UPPERCASE_OFFSET else: raise ValueError('%s is not a valid character' % char) def parse_chr(self, integer): if integer < 10: return chr(integer + DIGIT_OFFSET) elif 10 <= integer <= 35: return chr(integer + UPPERCASE_OFFSET) elif 36 <= integer < 62: return chr(integer + LOWERCASE_OFFSET) else: raise ValueError('%d is not a valid integer in the range of base %d' % (integer, Codec.BASE)) # Trie class Codec: BASE = 62 num_sender = 0 ALNUM = string.ascii_letters + '0123456789' d_map = {c: i for i, c in enumerate(ALNUM)} url = {} def encode(self, longUrl): pk = Codec.num_sender s_url = '' while pk > 0: pk, tail = divmod(pk, Codec.BASE) s_url = Codec.ALNUM[tail] + s_url Codec.url[pk] = longUrl Codec.num_sender += 1 if pk == 0: s_url = Codec.ALNUM[0] return s_url def decode(self, shortUrl): pk = sum(Codec.d_map[c]*Codec.BASE**i for i, c in enumerate(reversed(shortUrl))) return Codec.url[pk]
-
class Solution { public: // Encodes a URL to a shortened URL. string encode(string longUrl) { string v = to_string(++idx); m[v] = longUrl; return domain + v; } // Decodes a shortened URL to its original URL. string decode(string shortUrl) { int i = shortUrl.rfind('/') + 1; return m[shortUrl.substr(i, shortUrl.size() - i)]; } private: unordered_map<string, string> m; int idx = 0; string domain = "https://tinyurl.com/"; }; // Your Solution object will be instantiated and called as such: // Solution solution; // solution.decode(solution.encode(url));
-
type Codec struct { m map[int]string idx int } func Constructor() Codec { m := map[int]string{} return Codec{m, 0} } // Encodes a URL to a shortened URL. func (this *Codec) encode(longUrl string) string { this.idx++ this.m[this.idx] = longUrl return "https://tinyurl.com/" + strconv.Itoa(this.idx) } // Decodes a shortened URL to its original URL. func (this *Codec) decode(shortUrl string) string { i := strings.LastIndexByte(shortUrl, '/') v, _ := strconv.Atoi(shortUrl[i+1:]) return this.m[v] } /** * Your Codec object will be instantiated and called as such: * obj := Constructor(); * url := obj.encode(longUrl); * ans := obj.decode(url); */