Given a long url, make it shorter.
You should implement two methods:
longToShort(url)
Convert a long url to a short url which starts withhttp://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:
- 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
- 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; } }
No comments:
Post a Comment