535.Encode-and-Decode-TinyURL

535. Encode and Decode TinyURL

题目地址

https://leetcode.com/problems/encode-and-decode-tinyurl/

题目描述

Note: This is a companion problem to the System Design problem: Design TinyURL.
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.

代码

Approach 1: Using Simple Counter

使用Map对长URL进行映射，转变成integer.

或者再将Integer映射成其他字符

public class Codec {
  Map<Integer, String> map = new HashMap<>();
  int i = 0;
  // Encodes a URL to a shortened URL.
  public String encode(String longUrl) {
        map.put(i, longUrl);
    return "http://tinyurl.com" + i++;
  }

  // Decodes a shortened URL to its original URL.
  public String decode(String shortUrl) {
    String url = shortUrl.replace("http://tinyurl.com/", "");
        return map.get(Integer.parseInt(url));
  }
}

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

Approach #2 Variable-Length Encoding

class Codec {
  String chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
  HashMap<String, String> map = new HashMap<>();
  int count = 1;

  public String getString() {
    int c = count;
    StringBuilder sb = new StringBuilder();
    while (c > 0) {
      c--;
      sb.append(chars.charAt(c % 62));
      c /= 62;
    }

    return sb.toString();
  }

  public String encode(String longUrl) {
    String key = getString();
    map.put(key, longUrl);
    count++;
    return "http://tinyurl.com/" + key;
  }

  public String decode(String shortUrl) {
    String url = shortUrl.replace("http://tinyurl.com/", "");
       return map.get(url);
  }
}

Approach #3 Using Hashcode

class Codec {
  Map<Integer, String> map = new HashMap<>();

  public String encode(String longUrl) {
    map.put(longUrl.hashCode(), longUrl);
    return "http://tinyurl.com/" + longUrl.hashCode();
  }

  public String decode(String shortUrl) {
    String url = shortUrl.replace("http://tinyurl.com/", "");
    return map.get(Integer.parseInt(url));
  }
}

Approach #4 Using random number

class Codec {
  Map<Integer, String> map = new HashMap<>();
  Random r = new Random();
  int key = r.nextInt(Integer.MAX_VALUE);

  public String encode(String longUrl) {
    while (map.containsKey(key)) {
      key = r.nextInt(Integer.MAX_VALUE);
    }
    map.put(key, longUrl);
    return "http://tinyurl.com/" + key;
  }

  public String decode(String shortUrl) {
    String url = shortUrl.replace("http://tinyurl.com/", "");
       return map.get(integer.parseInt(url));
  }
}

Approach #5 Random fixed-length encoding

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