[数据结构与算法]LeetCode 535（C#）

题目

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 。

代码

• 直接寻址（哈希）

public class Codec 
{
    private const int K1 = 10007;
    private const int K2 = 1000000007;
    private Dictionary<string, int> url2Key = new Dictionary<string, int>();
    private Dictionary<int, string> key2Url = new Dictionary<int, string>();

    // Encodes a URL to a shortened URL
    public string encode(string longUrl)
    {
        if (url2Key.ContainsKey(longUrl))
            return "http://tinyurl.com/" + url2Key[longUrl];
        
        int key = 0;
        long b = 1;
        foreach (char c in longUrl)
        {
            key = (int)((long)key * b + c) % K2;
            b = (b * K1) % K2;
        }

        while (key2Url.ContainsKey(key))
            key++;
        
        url2Key.Add(longUrl, key);
        key2Url.Add(key, longUrl);

        return "http://tinyurl.com/" + key;
    }

    // Decodes a shortened URL to its original URL.
    public string decode(string shortUrl) 
    {
        int idx = shortUrl.LastIndexOf('/') + 1;
        int key = int.Parse(shortUrl[idx..]);
        return key2Url[key];
    }
}

• 拉链寻址（哈希）

public class Codec 
{
    private const int K1 = 10007;
    private const int K2 = 1000000007;
    private Dictionary<string, (int, int)> url2Key = 
        new Dictionary<string, (int, int)>();
    private Dictionary<int, IList<string>> key2Url = 
        new Dictionary<int, IList<string>>();

    // Encodes a URL to a shortened URL
    public string encode(string longUrl)
    {
        if (url2Key.ContainsKey(longUrl))
        {
            var key = url2Key[longUrl];
            return "http://tinyurl.com/" + key.Item1.ToString() + '.' + key.Item2.ToString();
        }
        
        int key1 = 0;
        long P = 1;
        foreach (char c in longUrl)
        {
            key1 = (int)((long)(key1 * P + c) % K2);
            P = P * K1 % K2;
        }

        if (!key2Url.ContainsKey(key1)) key2Url.Add(key1, new List<string>());
        key2Url[key1].Add(longUrl);

        int key2 = key2Url[key1].Count - 1;
        url2Key.Add(longUrl, (key1, key2));
        
        return "http://tinyurl.com/" + key1.ToString() + '.' + key2.ToString();
    }

    // Decodes a shortened URL to its original URL.
    public string decode(string shortUrl) 
    {
        string[] strs = shortUrl[(shortUrl.LastIndexOf('/') + 1)..].Split('.');
        int key1 = int.Parse(strs[0]);
        int key2 = int.Parse(strs[1]);

        return key2Url[key1][key2];
    }
}