535. encryption and decryption of tinyurl: design a URL simplification system

Title Description

This is a LeetCode Upper 「535. TinyURL Encryption and decryption 」 , The difficulty is 「 secondary 」.

Tag : 「 Hashtable 」、「 simulation 」

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 .

Tips ：

• Topic data assurance url Is an effective URL

simulation + Hashtable

For each longUrl We are all here. 「 Capital / Lowercase letters / Numbers 」 Medium random Bit as its mapping identifier , This requires the use of a hash table tiny2Origin For recording .

It also prevents the same longUrl Multiple calls , Make sure encode Service 「 Idempotency 」, Let's create an additional hash table origin2Tiny To record the correspondence between the original string and the mapping ID .

Code ：

public class Codec {
    Map<String, String> origin2Tiny = new HashMap<>(), tiny2Origin = new HashMap<>();
    String str = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890";
    String prefix = "https://acoier.com/tags/";
    int k = 6;
    Random random = new Random();
    public String encode(String longUrl) {
        while (!origin2Tiny.containsKey(longUrl)) {
            char[] cs = new char[k];
            for (int i = 0; i < k; i++) cs[i] = str.charAt(random.nextInt(str.length()));
            String cur = prefix + String.valueOf(cs);
            if (tiny2Origin.containsKey(cur)) continue;
            tiny2Origin.put(cur, longUrl);
            origin2Tiny.put(longUrl, cur);
        }
        return origin2Tiny.get(longUrl);
    }
    public String decode(String shortUrl) {
  return tiny2Origin.get(shortUrl);
    }
}

• Time complexity ： encode The operation complexity is , among Is the short string length , Pass in parameters for longUrl The length of （ Storing in the hash table requires calculation longUrl Hash value , This process needs to traverse longUrl）; decode The operation complexity is , among Pass in parameters for shortUrl The length of , This length is fixed to prefix The length of the add
• Spatial complexity ： , among Is the number of calls , Is the average longUrl length

Last

This is us. 「 Brush through LeetCode」 The first of the series No.535 piece , The series begins with 2021/01/01, As of the start date LeetCode I have in common 1916 questions , Part of it is a locked question , We will finish all the questions without lock first .

In this series , In addition to explaining the idea of solving problems , And give the most concise code possible . If the general solution is involved, there will be corresponding code templates .

In order to facilitate the students to debug and submit code on the computer , I've built a warehouse ：https://github.com/SharingSource/LogicStack-LeetCode .

In the warehouse address , You can see the links to the series 、 The corresponding code of the series 、LeetCode Links to the original problem and other preferred solutions .

More, more, more popular 「 written examination / interview 」 Relevant information can be found in the beautifully arranged Gather new bases