diff options
author | Jack Sangdahl <[email protected]> | 2025-01-08 17:22:01 +0100 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-08 17:22:01 +0100 |
commit | 04d1609e0d5f554d23c19bc0629d0c3d697a87a1 (patch) | |
tree | 64bab4b0e844dcdd158525aac0691d36d1e8bf4d | |
parent | f416afbe5c617eb8aeae025d0b2d73c60145dbd3 (diff) | |
download | leetcode-04d1609e0d5f554d23c19bc0629d0c3d697a87a1.tar.gz leetcode-04d1609e0d5f554d23c19bc0629d0c3d697a87a1.zip |
535. encode and decode tinyurl
-rw-r--r-- | encode_decode_tinyurl.c | 31 | ||||
-rw-r--r-- | encode_decode_tinyurl.cpp | 54 | ||||
-rw-r--r-- | encode_decode_tinyurl.py | 46 |
3 files changed, 111 insertions, 20 deletions
diff --git a/encode_decode_tinyurl.c b/encode_decode_tinyurl.c new file mode 100644 index 0000000..2c7ddf7 --- /dev/null +++ b/encode_decode_tinyurl.c @@ -0,0 +1,31 @@ +// 535. Encode and Decode TinyURL +#include "leetcode.h" + +/* + * tinyurl is a url shortening service where you enter a url such as + * https://looooooongurl.com 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. + */ + +char *encode(char *longUrl) { + char *e = longUrl + strlen(longUrl) - 1, + *tiny = (char *)calloc(10000, sizeof(char)); + while (*e-- != '/') + ; + strcat(strcpy(tiny, "https://tinyurl.com/"), e + 2); + strcpy(tiny + strlen(tiny) + 1, longUrl); + return tiny; +} + +char *decode(char *shortUrl) { return shortUrl + strlen(shortUrl) + 1; } + +int main() { + char *url = "https://leetcode.com/problems/design-tinyurl"; + char *enc = encode(url); + printf("%s\n", + decode(enc)); // expect: https://leetcode.com/problems/design-tinyurl + free(enc); +} diff --git a/encode_decode_tinyurl.cpp b/encode_decode_tinyurl.cpp index 7596c6a..d7b9d98 100644 --- a/encode_decode_tinyurl.cpp +++ b/encode_decode_tinyurl.cpp @@ -1,29 +1,43 @@ +// 535. Encode and Decode TinyURL #include "leetcode.h" +/* + * tinyurl is a url shortening service where you enter a url such as + * https://looooooongurl.com 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. + */ + class Solution { +private: + const string charset = + "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"; + map<string, string> url_code, code_url; + random_device rd; + public: - unordered_map<string, string> codeDB, urlDB; - const string chars = - "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; string encode(string longUrl) { - if (urlDB.find(longUrl) != urlDB.end()) - return urlDB[longUrl]; - string code = genCode(); - while (codeDB.find(code) != codeDB.end()) - code = genCode(); - codeDB[code] = longUrl; - urlDB[longUrl] = code; - return code; - } - string decode(string shortUrl) { return codeDB[shortUrl]; } - -private: - string genCode() { - string code = ""; - for (int i = 0; i < 6; i++) - code += chars[rand() % 62]; + string code; + if (!url_code.count(longUrl)) { + for (int i = 0; i < 6; i++) + code.push_back(charset[rd() % charset.size()]); + url_code.insert(pair<string, string>(longUrl, code)); + code_url.insert(pair<string, string>(code, longUrl)); + } else + code = url_code[longUrl]; return "http://tinyurl.com/" + code; } + string decode(string shortUrl) { + if (shortUrl.size() != 25 || !code_url.count(shortUrl.substr(19, 6))) + return ""; + return code_url[shortUrl.substr(19, 6)]; + } }; -int main() {} +int main() { + Solution obj; + cout << obj.decode(obj.encode("https://leetcode.com/problems/design-tinyurl")) + << endl; // expect: https://leetcode.com/problems/design-tinyurl +} diff --git a/encode_decode_tinyurl.py b/encode_decode_tinyurl.py new file mode 100644 index 0000000..c043ba0 --- /dev/null +++ b/encode_decode_tinyurl.py @@ -0,0 +1,46 @@ +# 535. Encode and Decode TinyURL +from string import ascii_letters +from random import choice + +""" +tinyurl is a url shortening service where you enter a url such as +https://looooooongurl.com 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. +""" + + +class Codec: + alphabet = ascii_letters + "0123456789" + + def __init__(self): + self.url_code = {} + self.code_url = {} + + def encode(self, longUrl): + """Encodes a URL to a shortened URL. + + :type longUrl: str + :rtype: str + """ + while longUrl not in self.url_code: + code = "".join(choice(Codec.alphabet) for _ in range(6)) + if code not in self.code_url: + self.code_url[code] = longUrl + self.url_code[longUrl] = code + return "http://tinyurl.com/" + self.url_code[longUrl] + + def decode(self, shortUrl): + """Decodes a shortened URL to its original URL. + + :type shortUrl: str + :rtype: str + """ + return self.code_url[shortUrl[-6:]] + + +if __name__ == "__main__": + obj = Codec() + print(obj.decode(obj.encode("https://leetcode.com/problems/design-tinyurl"))) |