关于程序员:535-TinyURL-的加密与解密-设计一个-URL-简化系统

这是 LeetCode 上的 535. TinyURL 的加密与解密 ，难度为中等。

Tag :「哈希表」、「模仿」

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^4$
题目数据保障 url 是一个无效的 URL

对于每个 longUrl 咱们都在「大写字母 / 小写字母 / 数字」中随机 $k = 6$ 位作为其映射标识，这须要应用一个哈希表 tiny2Origin 进行记录。

同时了避免雷同的 longUrl 屡次调用，确保 encode 服务的「幂等性」，咱们再额定建设哈希表 origin2Tiny 来记录原串和映射标识的对应关系。

代码：

public class Codec {Map<String, String> origin2Tiny = new HashMap<>(), tiny2Origin = new HashMap<>();
    String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
    String prefix = "https://acoier.com/tags/";
    int k = 6;
    Random random = new Random();
    public String encode(String longUrl) {while (!origin2Tiny.containsKey(longUrl)) {char[] cs = new char[k];
            for (int i = 0; i < k; i++) cs[i] = str.charAt(random.nextInt(str.length()));
            String cur = prefix + String.valueOf(cs);
            if (tiny2Origin.containsKey(cur)) continue;
            tiny2Origin.put(cur, longUrl);
            origin2Tiny.put(longUrl, cur);
        }
        return origin2Tiny.get(longUrl);
    }
    public String decode(String shortUrl) {return tiny2Origin.get(shortUrl);
    }
}

工夫复杂度：encode 操作复杂度为 $O(C + L)$，其中 $C = 6$ 为短串长度，$L$ 为传入参数 longUrl 的长度（存入哈希表须要计算 longUrl 哈希值，该过程须要遍历 longUrl）；decode 操作复杂度为 $O(C)$，其中 $L$ 为传入参数 shortUrl 的长度，该长度固定为 prefix 长度加 $6$
空间复杂度：$O(K \times L)$，其中 $K$ 为调用次数，$L$ 为均匀 longUrl 长度

这是咱们「刷穿 LeetCode」系列文章的第 No.535 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。

更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的合集新基地 🎉🎉

本文由 mdnice 多平台公布

关于程序员:535-TinyURL-的加密与解密-设计一个-URL-简化系统

题目形容

模仿 + 哈希表

最初