0535-TinyURL 的加密与解密

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:28 2023-09-13 16:06:28 Updated    

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 <= 104
  • 题目数据保证 url 是一个有效的 URL

前言

题目不要求相同的 URL 必须加密成同一个 TinyURL，因此本文的方法不满足相同的 URL 加密成同一个 TinyURL。如果想要实现相同的 URL 加密成同一个 TinyURL，则额外保存一个从 URL 到 TinyURL 的映射。

方法一：自增

  • Encode 函数

    使用自增 id 作为 longUrl 的键，每接收一个 longUrl 都将 id 加一，将键值对 (\textit{id}, \textit{longUrl}) 插入数据库 dataBase，然后返回带有 id 的字符串作为 shorUrl。

  • Decode 函数

    将 shortUrl 转换成对应的 key，然后在数据库 dataBase 中查找 key 对应的 longUrl。

[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Codec:
    def __init__(self):
        self.database = {}
        self.id = 0

    def encode(self, longUrl: str) -> str:
        self.id += 1
        self.database[self.id] = longUrl
        return "http://tinyurl.com/" + str(self.id)

    def decode(self, shortUrl: str) -> str:
        i = shortUrl.rfind('/')
        id = int(shortUrl[i + 1:])
        return self.database[id]
[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
private:
    unordered_map<int, string> dataBase;
    int id;

public:
    Solution() {
        id = 0;
    }

    string encode(string longUrl) {
        id++;
        dataBase[id] = longUrl;
        return string("http://tinyurl.com/") + to_string(id);
    }

    string decode(string shortUrl) {
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Codec {
    private Map<Integer, String> dataBase = new HashMap<Integer, String>();
    private int id;

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

    public String decode(String shortUrl) {
        int p = shortUrl.lastIndexOf('/') + 1;
        int key = Integer.parseInt(shortUrl.substring(p));
        return dataBase.get(key);
    }
}
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Codec {
    private Dictionary<int, string> dataBase = new Dictionary<int, string>();
    private int id;

    public string encode(string longUrl) {
        id++;
        if (!dataBase.ContainsKey(id)) {
            dataBase.Add(id, longUrl);
        } else {
            dataBase[id] = longUrl;
        }
        return "http://tinyurl.com/" + id;
    }

    public string decode(string shortUrl) {
        int p = shortUrl.LastIndexOf('/') + 1;
        int key = int.Parse(shortUrl.Substring(p, shortUrl.Length - p));
        return dataBase[key];
    }
}
[sol1-C]
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
typedef struct {
    int key;
    char *val;
    UT_hash_handle hh;
} HashItem;

HashItem *dataBase = NULL;
int id = 0;

char* encode(char* longUrl) {
    id++;
    HashItem * pEntry = NULL;
    HASH_FIND_INT(dataBase, &id, pEntry);
    if (NULL == pEntry) {
        pEntry = (HashItem *)malloc(sizeof(HashItem));
        pEntry->key = id;
        pEntry->val = longUrl;
        HASH_ADD_INT(dataBase, key, pEntry);
    }
    char *res = (char *)malloc(sizeof(char) * 64);
    sprintf(res, "%s%d", "http://tinyurl.com/", id); 
    return res;
}

char* decode(char* shortUrl) {
    char *p = shortUrl;
    char *last = shortUrl;
    while (last = strchr(p, '/')) {
        p = last + 1;
    }
    int key = atoi(p);
    HashItem * pEntry = NULL;
    HASH_FIND_INT(dataBase, &key, pEntry);
    if (NULL != pEntry) {
        return pEntry->val;
    }
    return NULL;
}

[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
var encode = function(longUrl) {
    this.dataBase = new Map();
    this.id = 0;
    this.id++;
    this.dataBase.set(this.id, longUrl);
    return "http://tinyurl.com/" + this.id;
};

var decode = function(shortUrl) {
    const p = shortUrl.lastIndexOf('/') + 1;
    const key = parseInt(shortUrl.substring(p));
    return this.dataBase.get(key);
};
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
type Codec struct {
    dataBase map[int]string
    id       int
}

func Constructor() Codec {
    return Codec{map[int]string{}, 0}
}

func (c *Codec) encode(longUrl string) string {
    c.id++
    c.dataBase[c.id] = longUrl
    return "http://tinyurl.com/" + strconv.Itoa(c.id)
}

func (c *Codec) decode(shortUrl string) string {
    i := strings.LastIndexByte(shortUrl, '/')
    id, _ := strconv.Atoi(shortUrl[i+1:])
    return c.dataBase[id]
}

复杂度分析

  • 时间复杂度：

    • Encode 函数：O(n)，其中 n 是字符串 longUrl 的长度。

    • Decode 函数：O(1)。我们当 shortUrl 当成有限长度的字符串看待。

  • 空间复杂度：

    • Encode 函数：O(n)。保存字符串 longUrl 需要 O(n) 的空间。

    • Decode 函数：O(1)。

方法二：哈希生成

  • Encode 函数

    设字符串 longUrl 的长度为 n，选择两个合适的质数 k_1 = 1117，k_2 = 10^9 + 7，使用以下方法来计算 longUrl 的哈希值：

    Hash} ( \textit{longUrl} ) = \big ( \sum^{n-1}_{i=0} \textit{longUrl}[i] \times k_1^i \big ) \bmod k_2

    将哈希值作为 longUrl 的 key，将键值对 (\textit{key}, \textit{longUrl}) 插入数据库 dataBase，然后返回带有 key 的字符串作为 shorUrl。

    发生哈希冲突时，我们采用线性探测再散列的方法，将 key 加一，直到没有冲突。相同的 longUrl 的哈希值相同，因此哈希冲突会频繁发生。为了避免这一点，我们使用一个额外的哈希表记录从 longUrl 到 key 的映射。

  • Decode 函数

    将 shortUrl 转换成对应的 key，然后在数据库 dataBase 中查找 key 对应的 longUrl。

[sol2-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
K1, K2 = 1117, 10 ** 9 + 7

class Codec:
    def __init__(self):
        self.dataBase = {}
        self.urlToKey = {}

    def encode(self, longUrl: str) -> str:
        if longUrl in self.urlToKey:
            return "http://tinyurl.com/" + str(self.urlToKey[longUrl])
        key, base = 0, 1
        for c in longUrl:
            key = (key + ord(c) * base) % K2
            base = (base * K1) % K2
        while key in self.dataBase:
            key = (key + 1) % K2
        self.dataBase[key] = longUrl
        self.urlToKey[longUrl] = key
        return "http://tinyurl.com/" + str(key)

    def decode(self, shortUrl: str) -> str:
        i = shortUrl.rfind('/')
        key = int(shortUrl[i + 1:])
        return self.dataBase[key]
[sol2-C++]
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
const long long k1 = 1117;
const long long k2 = 1e9 + 7;

class Solution {
private:
    unordered_map<int, string> dataBase;
    unordered_map<string, int> urlToKey;

public:
    Solution() {

    }

    string encode(string longUrl) {
        if (urlToKey.count(longUrl) > 0) {
            return string("http://tinyurl.com/") + to_string(urlToKey[longUrl]);
        }
        long long key = 0, base = 1;
        for (auto c : longUrl) {
            key = (key + c * base) % k2;
            base = (base * k1) % k2;
        }
        while (dataBase.count(key) > 0) {
            key = (key + 1) % k2;
        }
        dataBase[key] = longUrl;
        urlToKey[longUrl] = key;
        return string("http://tinyurl.com/") + to_string(key);
    }

    string decode(string shortUrl) {
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};
[sol2-Java]
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
public class Codec {
    static final int K1 = 1117;
    static final int K2 = 1000000007;
    private Map<Integer, String> dataBase = new HashMap<Integer, String>();
    private Map<String, Integer> urlToKey = new HashMap<String, Integer>();

    public String encode(String longUrl) {
        if (urlToKey.containsKey(longUrl)) {
            return "http://tinyurl.com/" + urlToKey.get(longUrl);
        }
        int key = 0;
        long base = 1;
        for (int i = 0; i < longUrl.length(); i++) {
            char c = longUrl.charAt(i);
            key = (int) ((key + (long) c * base) % K2);
            base = (base * K1) % K2;
        }
        while (dataBase.containsKey(key)) {
            key = (key + 1) % K2;
        }
        dataBase.put(key, longUrl);
        urlToKey.put(longUrl, key);
        return "http://tinyurl.com/" + key;
    }

    public String decode(String shortUrl) {
        int p = shortUrl.lastIndexOf('/') + 1;
        int key = Integer.parseInt(shortUrl.substring(p));
        return dataBase.get(key);
    }
}
[sol2-C#]
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
public class Codec {
    const int K1 = 1117;
    const int K2 = 1000000007;
    private Dictionary<int, string> dataBase = new Dictionary<int, string>();
    private Dictionary<string, int> urlToKey = new Dictionary<string, int>();

    public string encode(string longUrl) {
        if (urlToKey.ContainsKey(longUrl)) {
            return "http://tinyurl.com/" + urlToKey[longUrl];
        }
        int key = 0;
        long b = 1;
        foreach (char c in longUrl) {
            key = (int) ((key + (long) c * b) % K2);
            b = (b * K1) % K2;
        }
        while (dataBase.ContainsKey(key)) {
            key = (key + 1) % K2;
        }
        dataBase.Add(key, longUrl);
        urlToKey.Add(longUrl, key);
        return "http://tinyurl.com/" + key;
    }

    public string decode(string shortUrl) {
        int p = shortUrl.LastIndexOf('/') + 1;
        int key = int.Parse(shortUrl.Substring(p, shortUrl.Length - p));
        return dataBase[key];
    }
}
[sol2-C]
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
67
typedef struct {
    int key;
    char *val;
    UT_hash_handle hh;
} HashDataItem;

typedef struct {
    char *key;
    int val;
    UT_hash_handle hh;
} HashTokenItem;

const long long k1 = 1117;
const long long k2 = 1e9 + 7;
HashDataItem *dataBase = NULL;
HashTokenItem * urlToKey = NULL;

char* encode(char* longUrl) {
    HashTokenItem *pToken = NULL;
    HASH_FIND_STR(urlToKey, longUrl, pToken);
    if (NULL != pToken) {
        char *res = (char *)malloc(sizeof(char) * 64);
        sprintf(res, "%s%d", "http://tinyurl.com/", pToken->val); 
        return res;
    }
    long long key = 0, base = 1;
    int len = strlen(longUrl);
    for (int i = 0; i < len; i++) {
        char c = longUrl[i];
        key = (key + c * base) % k2;
        base = (base * k1) % k2;
    }
    HashDataItem * pEntry = NULL;
    do {
        pEntry = NULL;
        HASH_FIND_INT(dataBase, &key, pEntry);
        if (pEntry) {
            key = (key + 1) % k2;
        }
    } while(pEntry);
    pEntry = (HashDataItem *)malloc(sizeof(HashDataItem));
    pEntry->key = key;
    pEntry->val = longUrl;
    HASH_ADD_INT(dataBase, key, pEntry);
    pToken = (HashTokenItem *)malloc(sizeof(HashTokenItem));
    pToken->key = longUrl;
    pToken->val = key;
    HASH_ADD_STR(urlToKey, key, pToken);
    char *res = (char *)malloc(sizeof(char) * 64);
    sprintf(res, "%s%d", "http://tinyurl.com/", key); 
    return res;
}

char* decode(char* shortUrl) {
    char *p = shortUrl;
    char *last = shortUrl;
    while (last = strchr(p, '/')) {
        p = last + 1;
    }
    int key = atoi(p);
    HashDataItem * pEntry = NULL;
    HASH_FIND_INT(dataBase, &key, pEntry);
    if (NULL != pEntry) {
        return pEntry->val;
    }
    return NULL;
}
[sol2-JavaScript]
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
var encode = function(longUrl) {
    const K1 = 1117;
    const K2 = 1000000007;
    this.dataBase = new Map();
    this.urlToKey = new Map();

    if (this.urlToKey.has(longUrl)) {
            return "http://tinyurl.com/" + this.urlToKey.get(longUrl);
        }
        let key = 0;
        let base = 1;
        for (let i = 0; i < longUrl.length; i++) {
            const c = longUrl[i];
            key = (key + c * base) % K2;
            base = (base * K1) % K2;
        }
        while (dataBase.has(key)) {
            key = (key + 1) % K2;
        }
        dataBase.set(key, longUrl);
        urlToKey.set(longUrl, key);
        return "http://tinyurl.com/" + key;
};

var decode = function(shortUrl) {
    const p = shortUrl.lastIndexOf('/') + 1;
    const key = parseInt(shortUrl.substring(p));
    return this.dataBase.get(key);
};
[sol2-Golang]
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
const k1, k2 = 1117, 1e9 + 7

type Codec struct {
    dataBase map[int]string
    urlToKey map[string]int
}

func Constructor() Codec {
    return Codec{map[int]string{}, map[string]int{}}
}

func (c *Codec) encode(longUrl string) string {
    if key, ok := c.urlToKey[longUrl]; ok {
        return "http://tinyurl.com/" + strconv.Itoa(key)
    }
    key, base := 0, 1
    for _, c := range longUrl {
        key = (key + int(c)*base) % k2
        base = (base * k1) % k2
    }
    for c.dataBase[key] != "" {
        key = (key + 1) % k2
    }
    c.dataBase[key] = longUrl
    c.urlToKey[longUrl] = key
    return "http://tinyurl.com/" + strconv.Itoa(key)
}

func (c *Codec) decode(shortUrl string) string {
    i := strings.LastIndexByte(shortUrl, '/')
    key, _ := strconv.Atoi(shortUrl[i+1:])
    return c.dataBase[key]
}

复杂度分析

  • 时间复杂度：

    • Encode 函数：O(n)，其中 n 是字符串 longUrl 的长度。在数据量远小于 10^9 + 7 的情况下，发生哈希冲突的可能性十分小。

    • Decode 函数：O(1)。我们当 shortUrl 当成有限长度的字符串看待。

  • 空间复杂度：

    • Encode 函数：O(n)。保存字符串 longUrl 需要 O(n) 的空间。

    • Decode 函数：O(1)。

方法三：随机生成

  • Encode 函数

    使用一个随机生成的整数作为 longUrl 的 key，如果 key 已经重复，那么不断尝试随机生成整数，直到 key 唯一。将键值对 (\textit{key}, \textit{longUrl}) 插入数据库 dataBase，然后返回带有 key 的字符串作为 shorUrl。

  • Decode 函数

    将 shortUrl 转换成对应的 key，然后在数据库 dataBase 中查找 key 对应的 longUrl。

[sol3-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Codec:
    def __init__(self):
        self.dataBase = {}

    def encode(self, longUrl: str) -> str:
        while True:
            key = randrange(maxsize)
            if key not in self.dataBase:
                self.dataBase[key] = longUrl
                return "http://tinyurl.com/" + str(key)

    def decode(self, shortUrl: str) -> str:
        i = shortUrl.rfind('/')
        key = int(shortUrl[i + 1:])
        return self.dataBase[key]
[sol3-C++]
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
class Solution {
private:
    unordered_map<int, string> dataBase;

public:
    Solution() {
        srand(time(0));
    }

    string encode(string longUrl) {
        int key;
        while (true) {
            key = rand();
            if (dataBase.count(key) == 0) {
                break;
            }
        }
        dataBase[key] = longUrl;
        return string("http://tinyurl.com/") + to_string(key);
    }

    string decode(string shortUrl) {
        int p = shortUrl.rfind('/') + 1;
        int key = stoi(shortUrl.substr(p, int(shortUrl.size()) - p));
        return dataBase[key];
    }
};
[sol3-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Codec {
    private Map<Integer, String> dataBase = new HashMap<Integer, String>();
    private Random random = new Random();

    public String encode(String longUrl) {
        int key;
        while (true) {
            key = random.nextInt();
            if (!dataBase.containsKey(key)) {
                break;
            }
        }
        dataBase.put(key, longUrl);
        return "http://tinyurl.com/" + key;
    }

    public String decode(String shortUrl) {
        int p = shortUrl.lastIndexOf('/') + 1;
        int key = Integer.parseInt(shortUrl.substring(p));
        return dataBase.get(key);
    }
}
[sol3-C#]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class Codec {
    private Dictionary<int, string> dataBase = new Dictionary<int, string>();
    private Random random = new Random();

    public string encode(string longUrl) {
        int key;
        while (true) {
            key = random.Next();
            if (!dataBase.ContainsKey(key)) {
                break;
            }
        }
        dataBase.Add(key, longUrl);
        return "http://tinyurl.com/" + key;
    }

    public string decode(string shortUrl) {
        int p = shortUrl.LastIndexOf('/') + 1;
        int key = int.Parse(shortUrl.Substring(p, shortUrl.Length - p));
        return dataBase[key];
    }
}
[sol3-C]
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
typedef struct {
    int key;
    char *val;
    UT_hash_handle hh;
} HashItem;

HashItem *dataBase = NULL;

char* encode(char* longUrl) {
    srand(time(0));
    int key;
    HashItem * pEntry = NULL;
    while (true) {
        key = rand();
        pEntry = NULL;
        HASH_FIND_INT(dataBase, &key, pEntry);
        if (NULL == pEntry) {
            break;
        }
    }
    pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = longUrl;
    HASH_ADD_INT(dataBase, key, pEntry);
    char *res = (char *)malloc(sizeof(char) * 64);
    sprintf(res, "%s%d", "http://tinyurl.com/", key); 
    return res;
}

char* decode(char* shortUrl) {
    char *p = shortUrl;
    char *last = shortUrl;
    while (last = strchr(p, '/')) {
        p = last + 1;
    }
    int key = atoi(p);
    HashItem * pEntry = NULL;
    HASH_FIND_INT(dataBase, &key, pEntry);
    if (NULL != pEntry) {
        return pEntry->val;
    }
    return NULL;
}

[sol3-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
var encode = function(longUrl) {
    this.dataBase = new Map();
    let key;
    while (true) {
        key = Math.floor(Math.random() * (Number.MAX_SAFE_INTEGER));
        if (!dataBase.has(key)) {
            break;
        }
    }
    this.dataBase.set(key, longUrl);
    return "http://tinyurl.com/" + key;
};

var decode = function(shortUrl) {
    const p = shortUrl.lastIndexOf('/') + 1;
    const key = parseInt(shortUrl.substring(p));
    return this.dataBase.get(key);
};
[sol3-Golang]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import "math/rand"

type Codec map[int]string

func Constructor() Codec {
    return Codec{}
}

func (c Codec) encode(longUrl string) string {
    for {
        key := rand.Int()
        if c[key] == "" {
            c[key] = longUrl
            return "http://tinyurl.com/" + strconv.Itoa(key)
        }
    }
}

func (c Codec) decode(shortUrl string) string {
    i := strings.LastIndexByte(shortUrl, '/')
    key, _ := strconv.Atoi(shortUrl[i+1:])
    return c[key]
}

复杂度分析

  • 时间复杂度：

    • Encode 函数：O(n)，其中 n 是字符串 longUrl 的长度。在数据量远小于 2^{32 的情况下，随机生成的整数重复的可能性十分小。

    • Decode 函数：O(1)。我们当 shortUrl 当成有限长度的字符串看待。

  • 空间复杂度：

    • Encode 函数：O(n)。保存字符串 longUrl 需要 O(n) 的空间。

    • Decode 函数：O(1)。

 Comments
On this page
0535-TinyURL 的加密与解密