49 Encode and Decode TinyURL

devi

发布于 2021-08-18 16:19:34

1.1K0

题目

Note: This is a companion problem to the System Design problem: Design TinyURL.

TinyURL is a URL shortening service where you enter a URL such as https://leetcode.com/problems/design-tinyurl and it returns a short URL such as http://tinyurl.com/4e9iAk.

Design the encode and decode methods for the TinyURL service. There is no restriction on how your encode/decode algorithm should work. You just need to ensure that a URL can be encoded to a tiny URL and the tiny URL can be decoded to the original URL.

分析

题意：设计一个简化URL的编码算法，比如将https://leetcode.com/problems/design-tinyurl编码为http://tinyurl.com/4e9iAk，当然http://tinyurl.com/4e9iAk解码的结果也为https://leetcode.com/problems/design-tinyurl。

这个是开放性的题目，自行设计即可。个人想法（以https://leetcode.com/problems/design-tinyurl为例）： https://leetcode.com/保持原样。我们假设所有的URL都要进行编码，那么主域名就没有编码的必要了。

以https://leetcode.com/problems/design-tinyurl为例，个人觉得难点有两点： 1.xxx/design-tinyurl和xxx/design-tinyuri也应当被识别，因此url的识别粒度在单个符号的层面。 2.URL如何缩短–>26个字母+n个符号如何转为更少的符号表示–>如何保证26个字母+n个符号的转换过程可逆。

比如说1,2,3将其转为一个数的方法为1+2+3=6，但是6并不能唯一的转为1,2,3，因此这种方法不行。难点就在于如何缩短之后还能保证可逆？

有哪些运算是多元运算得出单个结果，并且该结果也能逆运算为多个元？百度了解了下，应该跟要使用压缩算法。了解了下zip算法，也有个想法，但是写了半天写不下去了。

去看看别人的做法。

看完别人的做法。。。看样子是我想多了。

算法

将原始的uri对应任意一个唯一的字符，存放到map中，如{原始uri：唯一字符}，并备份一份{唯一字符：原始uri}。
编码的时候就是`原始uri映射到唯一字符`，解码的时候用`唯一字符到原始uri的map`即可。

解答

public class Codec {
	//{识别字符：原始uri}
    Map<String, String> index = new HashMap<String, String>();
    //{原始uri，识别字符}
    Map<String, String> revIndex = new HashMap<String, String>();
    static String BASE_HOST = "http://tinyurl.com/";
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (revIndex.containsKey(longUrl)) return BASE_HOST + revIndex.get(longUrl);
        String charSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
        String key = null;
        do {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < 6; i++) {
                int r = (int) (Math.random() * charSet.length());
                sb.append(charSet.charAt(r));
            }
            key = sb.toString();
        } while (index.containsKey(key));
        index.put(key, longUrl);
        revIndex.put(longUrl, key);
        return BASE_HOST + key;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return index.get(shortUrl.replace(BASE_HOST, ""));
    }
}

简化版

    Map<Integer, String> map = new HashMap();
    String host = "http://tinyurl.com/";

    public String encode(String longUrl) {
      int key = longUrl.hashCode();
      map.put(key, longUrl);
      return host+key;
    }

    public String decode(String shortUrl) {
      int key = Integer.parseInt(shortUrl.replace(host,""));
      return map.get(key);
    }

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2020/03/14 ，如有侵权请联系 cloudcommunity@tencent.com 删除

php