LeetCode 535. TinyURL 的加密与解密 题解。

题目

535. TinyURL 的加密与解密

https://leetcode.cn/problems/encode-and-decode-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 是由同一个系统对象加密的。

自增id

思路

这是后端常用的手段，使用自增id来表示一个编码，也唯一标识一条数据。

自增id在不考虑安全性的情况下，可以作为实现成本较低的方案。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

/**
    * 执行用时：
    * 1 ms
    * , 在所有 Java 提交中击败了
    * 73.55%
    * 的用户
    * 内存消耗：
    * 41.5 MB
    * , 在所有 Java 提交中击败了
    * 59.23%
    * 的用户
    * 通过测试用例：
    * 739 / 739
    * <p>
    * 自增id
    */
class AutoIncrementIdCodec {

    int id;
    Map<String, String> short2Long;
    /**
        * 短链服务域名前缀
        */
    String prefix = "https://redolog.github.io/";

    public AutoIncrementIdCodec() {
        id = 0;
        short2Long = new HashMap<>();
    }

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        ++id;
        String shortUrl = String.valueOf(id);
        short2Long.put(shortUrl, longUrl);
        return prefix + shortUrl;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return short2Long.get(shortUrl.substring(shortUrl.lastIndexOf("/") + 1));
    }
}

复杂度

n：入参字符串长度

时间
  • encode：只需id递增，将长短映射放入map，O(1)。
  • decode：需遍历短链、截取，O(n)。
空间

映射占用链长级别的空间，占用O(n)。

随机串拼接

思路

使用

1

baseStr = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";

作为字符素材源，拼接固定长度的组合，一共有len(baseStr)^codeLen种排列，并且每个位置的字符可重复，整体编码不重复即可。

我们使用持久化的方式校验重复。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66

/**
    * 执行用时：
    * 3 ms
    * , 在所有 Java 提交中击败了
    * 54.45%
    * 的用户
    * 内存消耗：
    * 41.7 MB
    * , 在所有 Java 提交中击败了
    * 27.36%
    * 的用户
    * 通过测试用例：
    * 739 / 739
    */
class RandomKeyCodec {
    /**
        * 概率随机
        */
    ThreadLocalRandom random;
    /**
        * 生成素材串
        */
    String baseStr;
    /**
        * 存储映射
        */
    Map<String, String> short2Long;
    /**
        * 短链后缀长度
        */
    int codeLen;
    /**
        * 短链服务域名前缀
        */
    String prefix = "https://dragonsong.tech/";

    public RandomKeyCodec() {
        random = ThreadLocalRandom.current();
        baseStr = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
        short2Long = new HashMap<>();
        codeLen = 8;
    }

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        String shortCode;
        do {
            shortCode = gen(longUrl);
        } while (short2Long.containsKey(shortCode));
        short2Long.put(shortCode, longUrl);
        return prefix + shortCode;
    }

    private String gen(String longUrl) {
        char[] codeArr = new char[codeLen];
        for (int i = 0; i < codeLen; i++) {
            codeArr[i] = baseStr.charAt(random.nextInt(baseStr.length()));
        }
        return String.valueOf(codeArr);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return short2Long.get(shortUrl.substring(shortUrl.lastIndexOf("/") + 1));
    }
}

复杂度

n：入参字符串长度

时间
  • encode：取决于gen复杂度，考虑到冲突概率极低，每次gen，仅需拼接codeLen即八位的字符串，复杂度为O(codeLen)。
  • decode：需遍历短链、截取，O(n)。
空间

映射占用链长级别的空间，占用O(n)。

hashids

可以研究下 hashids 实现细节。