LeetCode535. TinyURL 的加密与解密

题目描述

本题目来自LeetCode上的『535. 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 是由同一个系统对象加密的。

示例1：

输入：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

题解1 - 自增键值

设置一个键值 $id$，对于一个新的 $longUrl$，将 $http://tinyurl.com/id$ 对应作为 $shortUrl$，然后将 $id$ 加一。
建立一个从 $shortUrl$ 到 $longUrl$ 的映射，即可根据 $shortUrl$ 得到对应的 $longUrl$。

代码

class Solution {
private:
    int id;
    unordered_map<string, string> short2long;
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        string str = "http://tinyurl.com/" + to_string(id++);
        short2long[str] = longUrl;
        return str;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return short2long[shortUrl];
    }
};

复杂度分析

时间复杂度：encode() 操作为 $O(n)$，decode() 操作为 $O(1)$
空间复杂度：encode() 操作为 $O(n)$，decode() 操作为 $O(1)$

题解2 - 哈希生成

将上述方法中的 $id$ 改为哈希值，可以使用 C++ 自带的 hash<K> 模板，或者其他任意一种方式（md5、rsa等）。

代码

class Solution {
private:
    unordered_map<string, string> short2long;
    hash<string> hashStr;
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        string hashCode = to_string(hashStr(longUrl));
        string str = "http://tinyurl.com/" + hashCode;
        short2long[hashCode] = longUrl;
        return str;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        string::size_type pos = shortUrl.find_last_of('/') + 1;
        return short2long[shortUrl.substr(pos)];
    }
};

复杂度分析

不考虑 hash<K> 的复杂度

时间复杂度：encode() 操作为 $O(n)$，decode() 操作为 $O(1)$
空间复杂度：encode() 操作为 $O(n)$，decode() 操作为 $O(1)$

题解3 - 不加密

发现直接返回竟然也能通过。不加密也是一种加密（。

代码

class Solution {
public:

    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        return longUrl;
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        return shortUrl;
    }
};