Java solution with the detailed explanation


  • 0
    L

    First of all, it may not be required for you to have only 7 characters to shorten the URL. However, with a base of 62 (0-9, a-z and A-Z), it covers enough for Leetcode testcases so I opted to use only 7 characters covering 42 bits using base of 62. I added randomness using nanotime and also a random function seeded with the nanotime. Please remember that you should avoid collison by running it continusly till you have successfully avoided a collison and generated a really new url. Here is the code:

    public class Codec {
        private final Map<String,String> map = new HashMap<>();
        private final String BASE = "http://tinyurl.com/";        
        
        // Encodes a URL to a shortened URL.
        public String encode(String longUrl) {
            if(longUrl==null) {
                return null;
            }
            
            String s = genHash(longUrl);
            while(map.put(s,longUrl)!=null) {
                s = genHash(longUrl);
            }
            
            return s;
        }
        
        private String genHash(String longUrl) {
            long curtime = System.nanoTime();
            Random r = new Random(curtime);
            long hash = curtime + r.nextLong() +  longUrl.hashCode();
            StringBuilder builder = new  StringBuilder();        
            builder.append(BASE);
            while(hash!=0) {
                builder.append(getCharAt((int)(hash%62)));
                hash = hash/62;
            }
            return builder.toString();
        }
    
        // Decodes a shortened URL to its original URL.
        public String decode(String shortUrl) {
            if(shortUrl==null) {
                return null;
            }
            return map.get(shortUrl);
        }
        
        private char getCharAt(int idx) {
            if(idx>=0 && idx<=9) {
                return (char)idx;
            }
            else if(idx>=10 && idx<=36) {
                return (char)('a' + idx-10);
            }
            else {
                return (char)('A' + idx-36);
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.