lintcode 232. Tiny Url

Given a long url, make it shorter.

You should implement two methods:

• longToShort(url) Convert a long url to a short url which starts with http://tiny.url/.
• shortToLong(url) Convert a short url to a long url.

You can design any shorten algorithm, the judge only cares about two things:

1. The short key's length should equal to 6 (without domain and slash). And the acceptable characters are [a-zA-Z0-9]. For example: abcD9E
2. No two long urls mapping to the same short url and no two short urls mapping to the same long url.

Example

Example 1:

Input: shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output: "http://www.lintcode.com/faq/?id=10"
Explanation: 
  When longToShort() called, you can return any short url.
  For example, "http://tiny.url/abcdef".
  And "http://tiny.url/ABCDEF" is ok as well.

Example 2:

Input:
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
  shortToLong(longToShort("http://www.lintcode.com/faq/?id=10"))
Output:
  "http://www.lintcode.com/faq/?id=10"
  "http://www.lintcode.com/faq/?id=10"

Code (Java):

public class TinyUrl {
    private GlobalCounter counter;
    private Map<Integer, String> idToLongURL;
    private Map<String, Integer> longURLToId;
    private String dict = "0123456789" + "abcdefghijklmnopqrstuvwxyz" + "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

    public TinyUrl() {
        counter = new GlobalCounter();
        idToLongURL = new HashMap<>();
        longURLToId = new HashMap<>();
    }

    public String longToShort(String url) {
        // write your code here
        // find if the short url already exists
        if (longURLToId.containsKey(url)) {
            int id = longURLToId.get(url);
            return idToShortURL(id);
        }
        
        int id = counter.getNext();
        String shortURL = idToShortURL(id);
        
        idToLongURL.put(id, url);
        longURLToId.put(url, id);
        
        return shortURL;
    }

    /*
     * @param url: a short url starts with http://tiny.url/
     * @return: a long url
     */
    public String shortToLong(String url) {
        // write your code here
        int id = shortURLToId(url);
        
        return idToLongURL.get(id);
    }
    
    
    private String idToShortURL(int id) {
        StringBuilder sb = new StringBuilder();
        while (id > 0) {
            sb.insert(0, dict.charAt(id % 62));
            id /= 62;
        }

        while (sb.length() < 6) {
            sb.insert(0, '0');
        }
        
        String shortURL = "http://tiny.url/" + sb.toString();
        
        return shortURL;
    }
    
    private int shortURLToId(String shortURL) {
        int id = 0;
        shortURL = shortURL.substring(shortURL.length() - 6);
        for (int i = 0; i < shortURL.length(); i++) {
            id = id * 62 + base62(shortURL.charAt(i));
        }
        
        return id;
    }
    
    private int base62(char c) {
        if (c >= '0' && c <= '9') {
            return c - '0';
        } else if (c >= 'a' && c <= 'z') {
            return c - 'a' + 10;
        } else if (c >= 'A' && c <= 'Z') {
            return c - 'A' + 36;
        }
        
        return 0;
    }
}

class GlobalCounter {
    private int counter;
    public GlobalCounter() {
        counter = 1;
    }

    public int getNext() {
        int next = counter;
        counter += 1;
        return next;
    }
}