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

random

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:]]

Counter

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]]

uuid

# 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).