哈希表题目：TinyURL 的加密与解密-Toy模板网

这篇具有很好参考价值的文章主要介绍了哈希表题目：TinyURL 的加密与解密。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

标题和出处

标题：TinyURL 的加密与解密

出处：535. TinyURL 的加密与解密

难度

7 级

题目描述

要求

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

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

实现 $\texttt{Codec}$ 类：

$\texttt{Codec()}$ 初始化系统对象。
$\texttt{String encode(String longUrl)}$ 根据给定的 $\texttt{longUrl}$ 返回 $\texttt{shortUrl}$ 。
$\texttt{String decode(String shortUrl)}$ 根据给定的 $\texttt{shortUrl}$ 返回原始的 $\texttt{longUrl}$ 。题目保证给定的 $\texttt{shortUrl}$ 由同一个对象加密。

示例

示例 1：

输入： $\texttt{url = "https://leetcode.com/problems/design-tinyurl"}$
输出： $\texttt{"https://leetcode.com/problems/design-tinyurl"}$
解释：
$\texttt{Codec obj = new Codec();}$
$\texttt{String tiny = obj.encode(url);}$ // 返回加密后的 tinyurl
$\texttt{String ans = obj.decode(tiny);}$ // 返回解密后的原始 url

数据范围

$\texttt{1} \le \texttt{url.length} \le \texttt{10}^\texttt{4}$
题目保证 $\texttt{url}$ 是有效的 URL

解法

思路和算法

这道题有多种实现方法，此处提供一种简单的计数实现方法。

维护一个计数器，初始时计数器的值为 $0$ 。每次加密时，将计数器的值加 $1$ ，在一个固定的 URL 前缀后面拼接上更新后的计数器的值，即可生成加密后的 TinyURL。

为了能够从 TinyURL 解密得到原始 URL，需要使用哈希表记录 TinyURL 和原始 URL 的对应关系，因此在加密操作中生成 TinyURL 之后，需要首先将 TinyURL 和 URL 存入哈希表，然后返回 TinyURL。

由于哈希表中记录了 TinyURL 和原始 URL 的对应关系，因此在解密时，只要从哈希表中找到 TinyURL 对应的原始 URL 并返回即可。

代码

public class Codec {
    static final String SHORT_PREFIX = "https://tinyurl.com/";
    Map<String, String> map = new HashMap<String, String>();
    int count = 0;

    public String encode(String longUrl) {
        count++;
        String shortUrl = SHORT_PREFIX + count;
        map.put(shortUrl, longUrl);
        return shortUrl;
    }

    public String decode(String shortUrl) {
        return map.get(shortUrl);
    }
}

复杂度分析

时间复杂度：构造方法和各项操作的时间复杂度都是 $O (1)$ 。构造方法为初始化操作，加密操作包括更新计数器、生成 TinyURL、将 TinyURL 和原始 URL 存入哈希表和返回 TinyURL，解密操作为从哈希表中得到 TinyURL 对应的原始 URL 并返回，时间复杂度都是 $O (1)$ 。这里将字符串操作的时间视为 $O (1)$ 。
空间复杂度： $O (n)$ ，其中 $n$ 是加密和解密的调用次数。需要使用两个哈希表记录每个 TinyURL 对应的原始 URL，哈希表中的元素个数取决于调用次数。