首页 > Web开发 > 详细

leetcode535 - Encode and Decode TinyURL - medium

时间:2018-09-25 13:39:16      阅读:200      评论:0      收藏:0      [点我收藏+]

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.

 

Map.
核心共同思想是,产生一个随机数作为当前原url的signature,把signature-original pair放入map后,以后你看到短url提取到signature,就可以再利用map提取到original url了。
产生随机数的方法:
1.count递增。 安全性有问题,而且不一定能缩短,int有限。
2.count递增,并且用26+26+10个字符dict组合上取余除法大发转化成String。和上面雷同,小好处是String可以把int缩短一点。
3.java自带的hashCode。str.hashCode()。缺点是可能会collision,然后你又很难临时创造新的不collision的hashCode。
4.random number + dict。好处是可以产生固定长度的。写一个取固定长度随机字符串作为signature的函数。比如长度为6,你就随机6次从dict里取到新char粘成一个signature,如果这个signature被用过了,就重新取一次signature直到成功。较为稳定不会忽长忽短,空间也足够62^6如果不够还可以比较方便地拓展。

 

细节:
1.为了增强shortURL的可读性,给随机数前面要加一些域名。decode的时候用到replace方法。

 

实现4:

public class Codec {
    
    private String dict = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    private int keyLength = 6;
    private Random rd = new Random();
    private Map<String, String> map = new HashMap<>();
    
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        String signature = getRand();
        while (map.containsKey(signature)) {
            signature = getRand();
        }
        map.put(signature, longUrl);
        return "http://tinyurl.com/" + signature;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(shortUrl.replace("http://tinyurl.com/", ""));
    }
    
    private String getRand() {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < keyLength; i++) {
            sb.append(dict.charAt(rd.nextInt(dict.length())));
        }
        return sb.toString();
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.decode(codec.encode(url));

 

leetcode535 - Encode and Decode TinyURL - medium

原文:https://www.cnblogs.com/jasminemzy/p/9698992.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!