TinyURL 的加密与解密

难度:

标签:

题目描述

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

代码结果

运行时间: 28 ms, 内存: 0.0 MB

/*
 * 思路：
 * 1. 使用一个ConcurrentHashMap来存储长URL到短URL的映射。
 * 2. 使用AtomicInteger来生成唯一的短URL。
 * 3. encode方法生成短URL并存储映射关系。
 * 4. decode方法通过短URL查找长URL。
 */
 
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicInteger;
 
public class Solution {
    private ConcurrentHashMap<String, String> map;
    private AtomicInteger id;
    private static final String BASE_URL = "http://tinyurl.com/";
 
    public Solution() {
        map = new ConcurrentHashMap<>();
        id = new AtomicInteger(1);
    }
 
    public String encode(String longUrl) {
        String shortUrl = BASE_URL + id.getAndIncrement();
        map.put(shortUrl, longUrl);
        return shortUrl;
    }
 
    public String decode(String shortUrl) {
        return map.get(shortUrl);
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(n)

代码细节讲解

🦆

在`encode`方法中，如果输入相同的`longUrl`多次，会产生怎样的结果？是否会为同一个`longUrl`生成不同的`tinyUrl`？

▷

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

🦆

在此题解中，计数器`count`是如何确保生成的短 URL 是唯一的？如果`count`超过了最大整数值会发生什么？

▷

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

🦆

字典`mapping`的键和值分别是什么，并且为什么选择`shortUrl`作为键而不是`longUrl`？

▷

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

🦆

如何处理和防止可能的安全问题，比如通过短 URL 推测或访问未授权的长 URL？

▷

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

TinyURL 的加密与解密

题目描述

代码结果

解释

代码细节讲解

相关问题