LeetCode 535（C＃）

subject

TinyURL It's a kind of URL Simplify services , such as ： When you enter a URL https://leetcode.com/problems/design-tinyurl when , It will return a simplified URL http://tinyurl.com/4e9iAk . Please design a class to encrypt and decrypt TinyURL .

There is no limit to how encryption and decryption algorithms are designed and operated , You just need to guarantee one URL Can be encrypted into a TinyURL , And this TinyURL It can be restored to the original by decryption URL .

Realization Solution class ：

Solution() initialization TinyURL System object .
String encode(String longUrl) return longUrl Corresponding TinyURL .
String decode(String shortUrl) return shortUrl The original URL . The subject data guarantees a given shortUrl Is encrypted by the same system object .

Example ：
Input ：url = “https://leetcode.com/problems/design-tinyurl”
Output ：“https://leetcode.com/problems/design-tinyurl”

explain ：
Solution obj = new Solution();
string tiny = obj.encode(url); // Returns the result of encryption TinyURL .
string ans = obj.decode(tiny); // Returns the original after decryption URL .

Code

• Direct addressing （ Hash ）

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];
    }
}

• Zipper addressing （ Hash ）

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];
    }
}