535 TinyURL 的加密与解密（哈希表）

àì夳堔傛蜴生んèń 2022-08-30 15:55 139阅读 0赞

**1. 问题描述：**

TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.  
要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个URL可以被加密成一个TinyURL，并且这个TinyURL可以用解密方法恢复成原本的URL。  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/encode-and-decode-tinyurl

**2. 思路分析：**

分析题目可以知道我们需要建立长串与短串之间的映射关系，这样才可以在长串与短传之间进行转换，这里可以使用**哈希表**来建立两个串之间的映射，我们可以使用随机化的方式来生成一个随机短串，具体可以在包括数字、小写字母、大写字母组合的62个字母中随机生成k个字符，相当于生成k位62进制的字符串，这样随机出的字符串是很少存在冲突的，我们在将长串映射到短串的过程中先判断一下哈希表中是否存在当前这个生成的子串，如果存在那么需要再次随机生成直到随机生成的短串在哈希表中是不存在的，我们在返回加密的短串的时候需要返回http://tinyurl.com/加上随机生成的短串这样才满足题目的要求，在解密的时候需要将之前加密返回的字符串解密为一开始的长串，因为存储到到哈希表中的是随机生成的k位短串，所以我们在哈希表中应该找的第19位之后的字符串，也即不包括http://tinyurl.com/中哈希表的值。

**3. 代码如下：**

import random
    
    
    class Codec:
        dic = dict()
    
        # 生成一个k位62进制的字符串
        def randomStr(self, k: int, s: str):
            res = ""
            while k > 0:
                res += s[random.randint(0, 61)]
                k -= 1
            return res
    
        # 主要的思路是使用哈希表将长串映射为一个短串
        def encode(self, longUrl: str) -> str:
            s = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
            t = "http://tinyurl.com/"
            while True:
                # 生成6位62进制的字符串的冲突已经很少了
                shortUrl = self.randomStr(6, s)
                if shortUrl not in self.dic:
                    self.dic[shortUrl] = longUrl
                    return t + shortUrl
            return ""
        
        # 这个方法主要是将解密之后的短串解密为原来的长串, 由于哈希表中存储的是生成的k位短传,所以需要找的是第19位开始的字符串
        def decode(self, shortUrl: str) -> str:
            return self.dic[shortUrl[19:]]