LeetCode Encode and Decode TinyURL

LeetCode Encode and Decode TinyURL

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.


实现短网址的功能,即把一个长的网址加密成短网址,并且能够把短网址还原为原来的长网址。

显然要用Hash,有多种方法,参考:https://leetcode.com/articles/encode-and-decode-tinyurl/

直接用一个计数器当key,相当于自己维护了一个长的url池,给每个url编了一个号。加密的时候把号码给他,解密的时候根据编号找到原始的url。代码如下:

class Solution {
private:
	unsigned long long m_ullCnt;
	unordered_map<unsigned long long, string> m_umHash;
public:
	Solution() :m_ullCnt(0) {};

	// Encodes a URL to a shortened URL.
	string encode(string longUrl) {
		m_umHash[m_ullCnt] = longUrl;
		return "http://tinyurl.com/" + to_string(m_ullCnt++);
	}

	// Decodes a shortened URL to its original URL.
	string decode(string shortUrl) {
		int id = atoi(shortUrl.substr(19).c_str());
		return m_umHash[id];
	}
};

本代码提交AC,用时9MS。

既然可以用计数器,也可以生成不重复的随机数作为key,不断random,和上面的解法类似。

还有一种生成key的方法,就是用STL自带的hash函数,把string hash成一个size_t作为key。注意要从短url中还原回hash值时,不能用atoi和atol,因为size_t可能是unsigned int,也可能和平台有关,所以必须用sscanf "%zu"的形式转换成size_t。

代码如下:

class Solution {
private:
	unordered_map<size_t, string> m_umHash;
public:
	// Encodes a URL to a shortened URL.
	string encode(string longUrl) {
		hash<string> h;
		m_umHash[h(longUrl)] = longUrl;
		return "http://tinyurl.com/" + to_string(h(longUrl));
	}

	// Decodes a shortened URL to its original URL.
	string decode(string shortUrl) {
		size_t id = 0;
		sscanf(shortUrl.substr(19).c_str(), "%zu", &id);
		return m_umHash[id];
	}
};

本代码提交AC,用时6MS。

Leave a Reply

Your email address will not be published. Required fields are marked *