实现TinyURL的加密与解密

题目描述
设计一个TinyURL服务，将长URL转换为短URL，并能通过短URL还原成长URL。要求实现两个方法：

• encode(longUrl)：将长URL转换为短URL
• decode(shortUrl)：将短URL还原为长URL

短URL格式为：http://tinyurl.com/ + 6位字符（包含大小写字母和数字）

解题思路分析

1. 我们需要建立长URL和短URL之间的双向映射关系
2. 使用哈希表存储长URL到短URL的映射（用于编码）
3. 使用另一个哈希表存储短URL到长URL的映射（用于解码）
4. 生成短URL时，使用随机生成的6位字符串作为后缀

详细解题步骤

步骤1：设计数据结构
我们需要两个哈希表来存储双向映射：

• long_to_short：键为长URL，值为短URL
• short_to_long：键为短URL，值为长URL

class Codec:
    def __init__(self):
        self.long_to_short = {}
        self.short_to_long = {}
        self.chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

步骤2：实现随机字符串生成
生成6位随机字符串作为短URL后缀：

    def get_random_string(self, length=6):
        import random
        return ''.join(random.choice(self.chars) for _ in range(length))

步骤3：实现编码方法encode

    def encode(self, longUrl: str) -> str:
        # 如果长URL已经存在映射，直接返回对应的短URL
        if longUrl in self.long_to_short:
            return self.long_to_short[longUrl]
        
        # 生成唯一的短URL后缀
        while True:
            short_suffix = self.get_random_string()
            short_url = f"http://tinyurl.com/{short_suffix}"
            
            # 确保生成的短URL是唯一的
            if short_url not in self.short_to_long:
                break
        
        # 建立双向映射
        self.long_to_short[longUrl] = short_url
        self.short_to_long[short_url] = longUrl
        
        return short_url

步骤4：实现解码方法decode

    def decode(self, shortUrl: str) -> str:
        # 直接从short_to_long哈希表中查找
        return self.short_to_long.get(shortUrl, "")

完整代码实现

import random

class Codec:
    def __init__(self):
        self.long_to_short = {}
        self.short_to_long = {}
        self.chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
        self.base_url = "http://tinyurl.com/"
    
    def get_random_string(self, length=6):
        return ''.join(random.choice(self.chars) for _ in range(length))
    
    def encode(self, longUrl):
        if longUrl in self.long_to_short:
            return self.long_to_short[longUrl]
        
        while True:
            short_suffix = self.get_random_string()
            short_url = self.base_url + short_suffix
            
            if short_url not in self.short_to_long:
                break
        
        self.long_to_short[longUrl] = short_url
        self.short_to_long[short_url] = longUrl
        return short_url
    
    def decode(self, shortUrl):
        return self.short_to_long.get(shortUrl, "")

# 使用示例
codec = Codec()
long_url = "https://leetcode.com/problems/design-tinyurl"
short_url = codec.encode(long_url)
print(f"短URL: {short_url}")
print(f"还原的长URL: {codec.decode(short_url)}")

算法分析

• 时间复杂度：encode和decode操作都是O(1)时间复杂度
• 空间复杂度：O(n)，其中n是存储的URL数量
• 哈希冲突处理：通过while循环确保生成的短URL唯一

优化考虑

1. 可以使用自增ID代替随机字符串，避免碰撞检查
2. 可以添加URL有效性验证
3. 可以考虑添加过期机制清理长时间未使用的映射

这个解决方案展示了哈希表在建立双向映射关系中的典型应用，是实际工程中URL缩短服务的简化版本。