LC.P535[TinyURL的加密与解密]

方法一：哈希表+模拟

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
public class Codec {

    String s = "1234567890abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
    int k = 6;
    Map<String, String> originToTinyMap = new HashMap<>(), tinyToOriginMap = new HashMap<>();
    Random random = new Random();
    String prefix = "https://byurself.github.io/";

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        while (!originToTinyMap.containsKey(longUrl)) {
            char[] cs = new char[k];
            for (int i = 0; i < k; ++i) {
                cs[i] = s.charAt(random.nextInt(s.length()));
            }
            String cur = prefix + String.valueOf(cs);
            // 已经存在，重新生成
            if (tinyToOriginMap.containsKey(cur)) continue;
            originToTinyMap.put(longUrl, cur); // 保证相同的 longUrl 多次调用，确保 encode 服务的 幂等性
            tinyToOriginMap.put(cur, longUrl);
        }
        return originToTinyMap.get(longUrl);
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return tinyToOriginMap.get(shortUrl);
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));
  • 时间复杂度：encode操作复杂度为$O(C + L)$，其中$C = 6$为随机生成的短串长度，$L$为传入的参数$longUrl$的长度(存入哈希表需要计算$longUrl$的哈希值，该过程需要遍历$longUrl$)；decode操作复杂度为$O(C)$，$C$为传入的参数$shortUrl$的长度，改长度固定为$prefix$长度加随机短串的长度6
  • 空间复杂度：$O(K \times L)$，其中$K$为调用次数，$L$为$longUrl$的平均长度