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):

?

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92

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;     } }