535. Encode and Decode TinyURL
Problem 535
https://leetcode.com/problems/encode-and-decode-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
class Codec:
alphabet = string.ascii_letters + '0123456789'
def __init__(self):
self.code2url = {}
self.url2code = {}
def encode(self, longUrl):
"""Encodes a URL to a shortened URL."""
while longUrl not in self.url2code:
code = ''.join(random.choice(Codec.alphabet) for _ in range(5) )
if code not in self.code2url:
self.code2url[ code ] = longUrl
self.url2code[ longUrl ] = code
return "http://tinyurl.com/" + self.url2code[ longUrl ]
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL."""
return self.code2url[shortUrl[-5:]]class Codec_counter:
def __init__(self):
self.code2url = {}
self.url2code = {}
self.count = 0
def encode(self, longUrl):
"""Encodes a URL to a shortened URL."""
while longUrl not in self.url2code:
self.count += 1
self.code2url[str(self.count)] = longUrl
self.url2code[longUrl] = str(self.count)
return "http://tinyurl.com/" + str(self.count)
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL."""
return self.code2url[shortUrl.split('/')[-1]]# solution by uuid3
import uuid
class Codec_uuid3:
def __init__(self):
self.code2url = {}
def encode(self, longUrl):
"""Encodes a URL to a shortened URL."""
code = uuid.uuid3(uuid.NAMESPACE_URL,str(longUrl))
self.code2url[ str(code) ] = longUrl
return "http://tinyurl.com/" + str(code)
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL."""
return self.code2url[shortUrl.split('/')[-1]]# solution by uuid4
import uuid
class Codec_uuid4:
#alphabet = string.ascii_letters + '0123456789'
alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
def __init__(self):
self.code2url = {}
def encode(self, longUrl):
"""Encodes a URL to a shortened URL."""
code = uuid.uuid4()
self.code2url[ str(code) ] = longUrl
return "http://tinyurl.com/" + str(code)
def decode(self, shortUrl):
"""Decodes a shortened URL to its original URL."""
return self.code2url[shortUrl.split('/')[-1]]uuid- in python
https://docs.python.org/2/library/uuid.html
uuid.uuid1([node[, clock_seq]])
從主機當前的 MAC address、時間、隨機數生成
優：保證全球唯一
缺：需要使用 Mac address 有安全性問題，有時會以 IP 來代替 Mac address
Generate a UUID from a host ID, sequence number, and the current time. If node is not given, getnode() is used to obtain the hardware address. If clock_seq is given, it is used as the sequence number; otherwise a random 14-bit sequence number is chosen.
uuid.uuid3(namespace, name)
透過輸入的字串（名字）和其空間的 MD5 散列值得到，只有在相同名字相同空間下才會是一樣的
Generate a UUID based on the MD5 hash of a namespace identifier (which is a UUID) and a name (which is a string).
uuid.uuid4()
隨機生成，其重複機率是有可能的
Generate a random UUID.
uuid.uuid5(namespace, name)
類似於 uuid3 ，但是是採用 SHA1 算法
Generate a UUID based on the SHA-1 hash of a namespace identifier (which is a UUID) and a name (which is a string).
Last updated