EncodeAndDecodeTinyURL [source code]

public class EncodeAndDecodeTinyURL {
static
/******************************************************************************/
public class Codec {
    Map<String, String> map = new HashMap<>();
    Set<String> set = new HashSet<>();

    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if (!set.contains(longUrl)) {
            int index = map.size() + 1;
            StringBuilder sb = new StringBuilder();
            while (index > 0) {
                int digit = index % 61;
                sb.append(encodeDigit(digit));
                index /= 61;
            }
            if (sb.length() < 6) {
                int gap = 6 - sb.length();
                for (int i = 0; i < gap; i++)
                    sb.append("Z");
            }
            String id = sb.reverse().toString();
            map.put(id, longUrl);
            set.add(longUrl);
            return "http://tinyurl.com/" + id;
        }
        return "";
    }

    public String encodeDigit(int digit) {
        if (digit <= 9) 
            return digit + "";
        else if (digit <= 35)
            return (char) (digit - 10 + 'a') + "";
        else 
            return (char) (digit - 35 + 'A') + "";
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        return map.get(shortUrl.substring(19, shortUrl.length()));
    }
}

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

    public static void main(String[] args) {
        EncodeAndDecodeTinyURL.Codec tester = new EncodeAndDecodeTinyURL.Codec();
    }
}

注意看这个题目的要求, 你最后需要做到的其实就是从short要能够返回到long就行了;

这个问题刚开始我半天没有思路, 是因为想的太复杂了, 这里的这个东西是一个system design的问题, 我们并不是指望你纯粹用一个类似, 就是一个单纯的算法就完成这个encoding and decoding, 就好像压缩算法; 我们指望你做的, 其实是有一个数据库的成分在里面的; 这个其实就简单很多了;

知道了这个问题之后, 这个题目总体的难度就显得很低了, 不够我为了和那个design的题目形成对应, 我这里的shortUrl里面的id还是固定的用的6位. editorial里面第一个答案直接就用一个数字当做id, 反正整体问题的本质是类似的;

最后的速度是8ms (48%), 还算可以接受;

submission上这种瓜批做法都被AC了:

public class Codec {  

    // Encodes a URL to a shortened URL.  
    public String encode(String longUrl) {  
        return longUrl;  
    }  

    // Decodes a shortened URL to its original URL.  
    public String decode(String shortUrl) {  
        return shortUrl;  
    }  
}

这个是editorial2, 做的feature跟我的这个是一样的, 但是他用了一个我没有想到的技巧:

public class Codec {  

    String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";  
    HashMap<String, String> map = new HashMap<>();  
    int count = 1;  

    public String getString() {  
        int c = count;  
        StringBuilder sb = new StringBuilder();  
        while (c > 0) {  
            c--;  
            sb.append(chars.charAt(c % 62));  
            c /= 62;  
        }  
        return sb.toString();  
    }  

    public String encode(String longUrl) {  
        String key = getString();  
        map.put(key, longUrl);  
        return "http://tinyurl.com/" + key;  
        count++;  
    }  

    public String decode(String shortUrl) {  
        return map.get(shortUrl.replace("http://tinyurl.com/", ""));  
    }  
}

就是他这个encode digit的完成方式十分巧妙; implementing lookup with literals其实这个前面已经碰到过好几次了, 这里没有想到; 尤其是碰到类似switch的(或者这里这种chained elif)的情况, 格外可以往这个方向上靠一下;

editorial3:

public class Codec {  
    Map<Integer, String> map = new HashMap<>();  

    public String encode(String longUrl) {  
        map.put(longUrl.hashCode(), longUrl);  
        return "http://tinyurl.com/" + longUrl.hashCode();  
    }  

    public String decode(String shortUrl) {  
        return map.get(Integer.parseInt(shortUrl.replace("http://tinyurl.com/", "")));  
    }  
}

直接用hashcode. 按照他的说法, JAVA默认的这个hashcode的实现方法其实就是一个base31的求和, s[0]是最高位;

editorial4直接用随机数;

另外注意他们这里这个replace的使用, 这个其实是很方便的: 我自己还要手动定位需要replace的位置;

这个是editorial的最后一个: 固定6位长度,然后用随机数:

public class Codec {  
    String alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";  
    HashMap<String, String> map = new HashMap<>();  
    Random rand = new Random();  
    String key = getRand();  

    public String getRand() {  
        StringBuilder sb = new StringBuilder();  
        for (int i = 0; i < 6; i++) {  
            sb.append(alphabet.charAt(rand.nextInt(62)));  
        }  
        return sb.toString();  
    }  

    public String encode(String longUrl) {  
        while (map.containsKey(key)) {  
            key = getRand();  
        }  
        map.put(key, longUrl);  
        return "http://tinyurl.com/" + key;  
    }  

    public String decode(String shortUrl) {  
        return map.get(shortUrl.replace("http://tinyurl.com/", ""));  
    }  
}

这个是discussion上面一个不错的解释:

below is the tiny url solution in java, also this is the similar method in industry. In industry, most of shorten url service is by database, one auto increasing long number as primary key. whenever a long url need to be shorten, append to the database, and return the primary key number. (the database is very easy to distribute to multiple machine like HBase, or even you can use the raw file system to store data and improve performance by shard and replica).
Note, it's meaningless to promise the same long url to be shorten as the same short url. if you do the promise and use something like hash to check existing, the benefit is must less than the cost.
Note: if you want the shorted url contains '0-9a-zA-Z' instead of '0-9', then you need to use 62 number system, not 10 number system(decimal) to convert the primary key number. like 123->'123' in decimal, 123->'1Z' in 62 number system (or '0001Z' for align).

public class Codec {  
    List<String> urls = new ArrayList<String>();  
    // Encodes a URL to a shortened URL.  
    public String encode(String longUrl) {  
        urls.add(longUrl);  
        return String.valueOf(urls.size()-1);  
    }  

    // Decodes a shortened URL to its original URL.  
    public String decode(String shortUrl) {  
        int index = Integer.valueOf(shortUrl);  
        return (index<urls.size())?urls.get(index):"";  
    }  
}

反正这个题目实际上就是属于一个我之前没有接触过的领域吧, 不要想的太复杂, 想要直接做一个compression算法, 那么这个题目其实就不难;

Problem Description

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.

Difficulty:Medium
Total Accepted:12.9K
Total Submissions:17.4K
Contributor: LeetCode
Companies
amazon google uber facebook
Related Topics
hash table math
Similar Questions
Design TinyURL