aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-08 17:22:01 +0100
committerJack Sangdahl <[email protected]>2025-01-08 17:22:01 +0100
commit04d1609e0d5f554d23c19bc0629d0c3d697a87a1 (patch)
tree64bab4b0e844dcdd158525aac0691d36d1e8bf4d
parentf416afbe5c617eb8aeae025d0b2d73c60145dbd3 (diff)
downloadleetcode-04d1609e0d5f554d23c19bc0629d0c3d697a87a1.tar.gz
leetcode-04d1609e0d5f554d23c19bc0629d0c3d697a87a1.zip
535. encode and decode tinyurl
-rw-r--r--encode_decode_tinyurl.c31
-rw-r--r--encode_decode_tinyurl.cpp54
-rw-r--r--encode_decode_tinyurl.py46
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")))