> For the complete documentation index, see [llms.txt](https://shuati.gitbook.io/crack-lintcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://shuati.gitbook.io/crack-lintcode/linkedin/encode-and-decode-tinyurl.md).

# Encode and Decode TinyURL

> Note: This is a companion problem to the [System Design](https://leetcode.com/discuss/interview-question/system-design/) problem: [Design TinyURL](https://leetcode.com/discuss/interview-question/124658/Design-a-URL-Shortener-\(-TinyURL-\)-System/).

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.

```java
public class Codec {
    
    private Map<String,String> short2long;
    private Map<String,String> long2short;
    private String dic;
    
    public Codec(){
        short2long = new HashMap<>();
        long2short = new HashMap<>();
        dic = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
        short2long.clear();
        long2short.clear();
    }
    // Encodes a URL to a shortened URL.
    public String encode(String longUrl) {
        if(long2short.containsKey(longUrl)){
            return "http://tinyurl.com/"+long2short.get(longUrl);
        }
        
        int index = 0;
        Random r = new Random();
        String randomStr = "";
        for(int i =0; i < 6;i++){
            randomStr += dic.charAt(r.nextInt(62));
        }
        
        while(short2long.containsKey(randomStr)){

            int rdNum = r.nextInt(62);
            randomStr = randomStr.substring(0,index) + dic.charAt(rdNum) + randomStr.substring(index+1);
            //random string length 6
            index = (index + 1) % 5;
        }
        
        long2short.put(longUrl,randomStr);
        short2long.put(randomStr,longUrl);
        
        return "http://tinyurl.com/"+randomStr;
    }

    // Decodes a shortened URL to its original URL.
    public String decode(String shortUrl) {
        String str = shortUrl.substring(shortUrl.lastIndexOf("/")+1);
        
        return short2long.containsKey(str)  ? short2long.get(str) : shortUrl;
    }
}

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

* The number of URLs that can be encoded is quite large in this case, nearly of the order (10+26\*2)^6(10+26∗2)6.
* The length of the encoded URLs is fixed to 6 units, which is a significant reduction for very large URLs.
* The performance of this scheme is quite good, due to a very less probability of repeated same codes generated.
* We can increase the number of encodings possible as well, by increasing the length of the encoded strings. Thus, there exists a tradeoff between the length of the code and the number of encodings possible.
* Predicting the encoding isn't possible in this scheme since random numbers are used.

```java

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/", ""));
    }
}

```