LeetCode 535.TinyURL 的加密与解密

发表于 | 分类于 |

哈希表使用 O(N) 空间复杂度存储数据，并且以 O(1) 时间复杂度求解问题。

  • Java 中的 HashSet 用于存储一个集合，可以查找元素是否在集合中。如果元素有穷，并且范围不大，那么可以用一个布尔数组来存储一个元素是否存在。例如对于只有小写字符的元素，就可以用一个长度为 26 的布尔数组来存储一个字符集合，使得空间复杂度降低为 O(1)。
  • Java 中的 HashMap 主要用于映射关系，从而把两个元素联系起来。HashMap 也可以用来对元素进行计数统计，此时键为元素，值为计数。和 HashSet 类似，如果元素有穷并且范围不大，可以用整型数组来进行统计。在对一个内容进行压缩或者其它转换时，利用 HashMap 可以把原始内容和转换后的内容联系起来。例如在一个简化 url 的系统中 Leetcdoe : 535. Encode and Decode TinyURL (Medium)

535.TinyURL 的加密与解密

535.Encode and Decode TinyURL (Medium)

LeetCode - TinyURL 的加密与解密

题目描述

TinyURL是一种URL简化服务， 比如：当你输入一个URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的URL http://tinyurl.com/4e9iAk.

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

解题思路

解法很多，但一般不作为编程题出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//代码简洁之道
public class Codec {
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        return longUrl;
    }
    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return shortUrl;
    }
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

简单计数法

为了加密 URL，我们使用计数器 (i) ，每遇到一个新的 URL 都加一。我们将 URL 与它的次数 i 放在哈希表 HashMap 中，这样我们在稍后的解密中可以轻易地获得原本的 URL。

  • 可以加密解密的 URL 数目受限于 int 所能表示的范围。

  • 如果超过 int 个 URL 需要被加密，那么超过范围的整数会覆盖之前存储的 URL，导致算法失效。

  • URL 的长度不一定比输入的 longURL 短。它只与加密的 URL 被加密的顺序有关。

  • 这个方法的问题是预测下一个会产生的加密 URL 非常容易，因为产生几个 URL 后很容易推测出生成的模式。

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Codec {
    Map<Integer, String> map = new HashMap<>();
    int i = 0;

    public String encode(String longUrl) {
        map.put(i, longUrl);
        return "http://tinyurl.com/" + i++;
    }

    public String decode(String shortUrl) {
        return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));
    }
}

随机固定长度加密（通用解法）

在这种方法中，使用数字和字母表集合来为 URL 生成加密结果。这种方法中，加密后的长度固定是 6 位。如果产生出来的加密结果与之前产生的结果一样，就换一个新的加密结果。

  • 可加密的 URL 数目非常大，几乎是$(10+26*2)^6$级别。

  • 加密 URL 的长度固定是 6，这相比于能加密的字符串数目是极大的缩减优化。

  • 这个方法的表现非常好，因为几乎不可能产生相同加密结果。

  • 我们也可以通过增加加密字符串的长度来增加加密结果的数目。因此，在加密字符串的长度和可加密的字符串数目之间我们需要做一个权衡。

  • 根据加密 URL 预测加密结果几乎是不可能的，因为使用了随机数。

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
public class Codec {
    String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    HashMap<String, String> map = new HashMap<>();
    Random rand = new Random();
    String key = getRand();

    public String getRand() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 6; i++) {
            sb.append(alphabet.charAt(rand.nextInt(62)));
        }
        return sb.toString();
    }

    public String encode(String longUrl) {
        while (map.containsKey(key)) {
            key = getRand();
        }
        map.put(key, longUrl);
        return "http://tinyurl.com/" + key;
    }

    public String decode(String shortUrl) {
        return map.get(shortUrl.replace("http://tinyurl.com/", ""));
    }
}