grid47 Exploring patterns and algorithms
Sep 14, 2024
7 min read
Solution to LeetCode 535: Encode and Decode TinyURL Problem
Design a URL shortening system where you can encode a long URL into a shortened URL and decode it back to the original URL. The system should guarantee that the original URL can always be retrieved using the shortened version.
Problem
Approach
Steps
Complexity
Input: The input consists of a valid long URL (string) that needs to be encoded into a shortened version. The input string will contain a valid URL of length between 1 and 10^4 characters.
• Explanation: The long URL "https://example.com/article/12345" is encoded into a shorter version, such as "http://tinyurl.com/4e9iAk", which can be decoded back to the original URL.
Approach: To solve this problem, we can use a hashmap to store the original URL and its corresponding shortened URL. A random string generator will be used to ensure uniqueness for the shortened URLs.
Observations:
• A unique identifier (short code) needs to be generated for each long URL to ensure that each encoded URL maps to a unique decoded URL.
• Using a random character set will allow us to generate short and unique codes for each URL.
Steps:
• Create a random string generator that will produce a short code of fixed length (e.g., 6 characters).
• Use two hashmaps: one for mapping long URLs to short codes and the other for mapping short codes back to long URLs.
• When encoding, check if the long URL has already been encoded and use the existing code if available. Otherwise, generate a new code and store the mapping.
• When decoding, extract the code from the short URL and use the second hashmap to retrieve the original URL.
Empty Inputs:
• Ensure that empty URLs are handled properly. However, in this problem, the input will always be a valid URL.
Large Inputs:
• The system should handle long URLs up to 10^4 characters efficiently.
Special Values:
• Consider the case where multiple URLs map to the same shortened URL. This should not happen due to the uniqueness of the generated short codes.
Constraints:
• Make sure the system handles all edge cases, including valid URLs, large inputs, and properly handles the mappings.
classSolution {
const string charset ="abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
random_device rd;
map<string, string> url_code, code_url;
public:// Encodes a URL to a shortened URL.
string encode(string longUrl) {
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;
}
// Decodes a shortened URL to its original URL.
string decode(string shortUrl) {
if(shortUrl.size() !=25||!code_url.count(shortUrl.substr(19,6)))
return"";
return code_url[shortUrl.substr(19,6)];
}
};
// Your Solution object will be instantiated and called as such:
// Solution solution;
1 : Class Definition
classSolution {
Defines the `Solution` class which contains the encoding and decoding methods for URL shortening.
