「微软」2023 开刷 535 ～ 编码解码短 URL

基本信息

• 题号：535
• 题厂：微软
• 难度系数：中

已知一个 URL，自定义「编码」「解码」算法，生成短 URL。原 URL 和生成的短 URL 可以编码解码查询……

例如 "https://leetcode.com/problems/design-tinyurl"
编码后输出 "http://tinyurl.com/4e9iAk" 为题目要求的短 URL

输入编码后的短 URL "http://tinyurl.com/4e9iAk"，可以解码回原 URL —— "https://leetcode.com/problems/design-tinyurl"

背景介绍 - TinyUrl 「系统设计」入门经典题

在 TinyUrl 系统设计题中，我们需要设计一个数据库，存放 「Tiny Url - Origin Url」的对应表单；

同时还需要设计各种 component 让用户可以从万千数据行中迅速找到自己的 TinyUrl 再指向原装 Url；以及新用户如何创建「Tiny Url - Origin Url」的 entry；过期的 TinyUrl 如何从系统删除……问题 🤪；

在考试过程中，我们还需要和考官充分讨论系统需要 handle 的用户流量以及 Url 数量，来决定编码的长度。例如：XX 位 「0-9」「a-z」……粗略估算数据库可以提供 Url 存量……

但是，作为 TinyUrl 延伸出来的算法题，这里我们不需要考虑有多少用户，需要存放多少 Url……只需要保证编码解码的一致和唯一性即可……

解题思路

• 弄明白题目题目需求后，为了保证唯一性和一致型，很容易想到 HashMap 需要出场解题；
• 想到 HashMap 后，下一步需要思考如何保证 HashMap 里 key 的一致性。这里可以用常规的 random 方法随机生成，也可以直接 1 2 3 4 5……排下去

class Codec:
    # 初始两个 HashMap：encodeMap「longUrl，shortUrl」，decodeMap「shortUrl，longUrl」。
    # 再创建一个 base url 备用……
    def __init__(self):
        self.encodeMap = {}
        self.decodeMap = {}
        self.base = "http://tinyurl.com/"

    # 当检测到需要创建新的 TinyUrl 时，编码的 key 为当前 HashMap 长度➕ 1（最简单的一种编法🥴）
    def encode(self, longUrl: str) -> str:
        """Encodes a URL to a shortened URL.
        """
        if longUrl not in self.encodeMap:
            url = self.base + str(len(self.encodeMap) + 1)
            self.encodeMap[longUrl] = url
            self.decodeMap[url] = longUrl
            return url
        else:
            return self.encodeMap[longUrl]
        
    # 解码非常简单……
    def decode(self, shortUrl: str) -> str:
        """Decodes a shortened URL to its original URL.
        """
        if shortUrl in self.decodeMap:
            return self.decodeMap[shortUrl]
        else:
            return "Url not found..."

Constraints

• 1 <= url.length <= 104
• url is guranteed to be a valid URL.

测试

• 随便放几个去编码解码……
• ……

Big O

• 时间复杂度：O（1），HashMap 查找复杂度是 1 🥲
• 空间复杂度： O（n）算上创建了 HashMap 🥲

总结

• 刨除 TinyUrl 系统设计题目背景，本题的算法解题思路部分应该算简单档才是……
• 然鹅欲解此题，和有没有 TinyUrl 系统设计背景知识无关……