[LeetCode] Challenge log 535

Posted on |
535. Encode and Decode TinyURL

https://leetcode.com/problems/encode-and-decode-tinyurl/description/

  1. Solution1: Use increasing numbers to mark tiny urls; actual urls are saved in a indexed list. (If want letters, can transfer the number into 62-based)
  2. Alternative: Genrate random 6-places string as tiny url. Two dictionaries to allow mapping in two ways and no duplicate.

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.

Soulution:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
### s1 ###

class Codec:
    def __init__(self):
        self.urls = []
    
    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.
        
        :type longUrl: str
        :rtype: str
        """
        self.urls.append(longUrl)
        return 'http://tinyurl.com/' + '{:0>6d}'.format(len(self.urls)-1)

    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.
        
        :type shortUrl: str
        :rtype: str
        """
        index = int(shortUrl[-6:])
        return self.urls[index]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
### s2 ###
import random
class Codec:
    
    alphabet = string.ascii_letters + '0123456789'
    
    def __init__(self):
        self.long = dict()
        self.tiny = dict()
        
    def encode(self, longUrl):
        """Encodes a URL to a shortened URL.
        
        :type longUrl: str
        :rtype: str
        """
        if longUrl in self.long: return self.long[longUrl]
        while True:
            tiny = ''.join([random.choice(Codec.alphabet) for i in range(6)])
            if tiny not in self.tiny: break
        self.long[longUrl] = tiny
        self.tiny[tiny] = longUrl
        return 'http://tinyurl.com/' + tiny

    def decode(self, shortUrl):
        """Decodes a shortened URL to its original URL.
        
        :type shortUrl: str
        :rtype: str
        """
        tiny = shortUrl[-6:]
        return self.tiny[tiny]

# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))
0%