LeetCode 题解工作台
TinyURL 的加密与解密
TinyURL 是一种 URL 简化服务， 比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk 。请你设计一个类来加密与解密 TinyURL 。 加密和…
4
题型
4
代码语言
3
相关题
当前训练重点
中等 · 哈希·表·结合·string
答案摘要
class Codec: def __init__(self):
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·表·结合·string 题型思路
题目描述
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 <= 104- 题目数据保证
url是一个有效的 URL
解题思路
方法一：哈希表
class Codec:
def __init__(self):
self.m = defaultdict()
self.idx = 0
self.domain = 'https://tinyurl.com/'
def encode(self, longUrl: str) -> str:
"""Encodes a URL to a shortened URL."""
self.idx += 1
self.m[str(self.idx)] = longUrl
return f'{self.domain}{self.idx}'
def decode(self, shortUrl: str) -> str:
"""Decodes a shortened URL to its original URL."""
idx = shortUrl.split('/')[-1]
return self.m[idx]
# Your Codec object will be instantiated and called as such:
# codec = Codec()
# codec.decode(codec.encode(url))
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on the hash table's average lookup and insertion operations, which are O(1). Space complexity is determined by the number of unique URLs stored in the hash table, with O(n) space required, where n is the number of URLs encoded. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for the candidate's ability to explain how hash tables are used for URL mapping.
- question_mark
Check for efficiency in handling edge cases and ensuring minimal collision between generated keys.
- question_mark
Test the candidate's understanding of string manipulation and how it's applied in encoding and decoding.
常见陷阱
外企场景- error
Using a weak hash function that results in many collisions, which can lead to inefficient performance.
- error
Not accounting for edge cases, such as URLs with similar patterns or large URLs.
- error
Failing to ensure that the decode method correctly retrieves the original URL after encoding.
进阶变体
外企场景- arrow_right_alt
Allowing customization of the URL shortening scheme by using different hash functions.
- arrow_right_alt
Handling URLs with special characters or query parameters in a more robust way.
- arrow_right_alt
Supporting a batch encoding and decoding operation to handle multiple URLs at once.