TinyURL 的加密与解密

难度: Medium

TinyURL 是一种 URL 简化服务，比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。

加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL ，并且这个 TinyURL 可以用解密方法恢复成原本的 URL 。

实现 Solution 类：

Solution() 初始化 TinyURL 系统对象。
String encode(String longUrl) 返回 longUrl 对应的 TinyURL 。
String decode(String shortUrl) 返回 shortUrl 原本的 URL 。题目数据保证给定的 shortUrl 是由同一个系统对象加密的。

示例：

输入：url = "https://leetcode.com/problems/design-tinyurl"
输出："https://leetcode.com/problems/design-tinyurl"

解释：
Solution obj = new Solution();
string tiny = obj.encode(url); // 返回加密后得到的 TinyURL 。
string ans = obj.decode(tiny); // 返回解密后得到的原本的 URL 。

提示：

1 <= url.length <= 10⁴
题目数据保证 url 是一个有效的 URL

Submission

运行时间: 28 ms

内存: 0.0 MB

class Codec:

    def __init__(self):
        self.mapping = {}
        self.count = 0
    
    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        temp_str = 'http://tinyurl.com/' + str(self.count)
        self.mapping[temp_str] = longUrl
        self.count += 1
        return temp_str

    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        return self.mapping[shortUrl]

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

Explain

本题解通过使用一个字典（mapping）来实现 TinyURL 的加密与解密。每次调用 encode 方法，都会使用一个递增的计数器（count）作为 TinyURL 的后缀，确保每个长 URL 对应一个唯一的短 URL。这个短 URL 将被存储在字典中，其键是新生成的短 URL，值是原始的长 URL。解码方法 decode 只需简单地通过短 URL 查找字典，返回相应的长 URL。

时间复杂度: O(1)

空间复杂度: O(n)

class Codec:

    def __init__(self):
        self.mapping = {}  # 初始化用于存储长 URL 和短 URL 映射的字典
        self.count = 0  # 初始化计数器用于生成唯一的短 URL 后缀
    
    def encode(self, longUrl: str) -> str:
        \"\"\"Encodes a URL to a shortened URL.\"\"\"
        temp_str = 'http://tinyurl.com/' + str(self.count)  # 生成新的短 URL
        self.mapping[temp_str] = longUrl  # 在字典中存储短 URL 到长 URL 的映射
        self.count += 1  # 更新计数器
        return temp_str  # 返回生成的短 URL

    def decode(self, shortUrl: str) -> str:
        \"\"\"Decodes a shortened URL to its original URL.\"\"\"
        return self.mapping[shortUrl]  # 通过短 URL 从字典中找到并返回对应的长 URL

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

Explore

在`encode`方法中，每次调用该方法都会递增计数器`count`并生成一个新的短 URL，即使输入的`longUrl`是相同的。因此，对于相同的`longUrl`，每次调用`encode`都会生成不同的`tinyUrl`。这样做虽然可以保证短 URL 的唯一性，但却不是最优的空间利用方式，因为相同的长 URL 不应该映射到多个短 URL。

在此题解中，计数器`count`从0开始，并且每次调用`encode`方法时递增。因为`count`每次都递增，所以每个生成的短 URL (`tinyurl.com/<count>`) 都是独一无二的。如果`count`超过了最大整数值，程序可能会遇到整数溢出的问题，这将导致生成重复的短 URL 或程序崩溃。在实际应用中，应该考虑设置一个更高效和安全的计数机制或使用其他方法生成唯一键。

在这个题解中，字典`mapping`的键是短 URL (`shortUrl`)，而值是对应的长 URL (`longUrl`)。选择`shortUrl`作为键而不是`longUrl`的原因在于解码过程的需求：解码方法`decode`需要通过短 URL 快速找到对应的长 URL。如果使用长 URL 作为键，那么在解码过程中就无法直接通过短 URL 获取长 URL，这将导致解码效率降低。

为了防止通过短 URL 推测或访问未授权的长 URL，可以采用以下几种策略：1. 使用随机或加密的字符串作为短 URL 的一部分，而不仅仅是递增数，这样可以增加猜测的难度。2. 对于敏感内容的长 URL，可以引入访问控制机制，如仅允许特定用户访问。3. 对于生成的短 URL，可以考虑设置过期时间，过期后短 URL 不再有效。这些措施可以有效提高系统的安全性，并防止未授权访问。