原題
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.
解析
TinyURL編碼/解碼
我的解法
LEETCODE、Medium難度的題。。也是只有思路沒有實現。。
我一開始的思路是有問題的,還嘗試找出一種算法可以讓長鏈和短鏈一一對應,但這種算法不存在,除非短鏈不限長度,但這樣就失去了意義
一般的短鏈都是域名+6位長度的隨機碼組成,試想所有大小寫+數字一共62個,那最多也只有62^6個短鏈,所以根本不能滿足無限多的長鏈
查了一些資料,網上的解法大致分三種:
算法一(超復雜。。覺得沒必要)
將長鏈進行md5加鹽編碼,所得32位;
8個一組(共4組),按16進制與0x3fffffff(30個1)與,即取后30位,忽略其他位;
30位分成6段,每段5位的數字作為字符表62個字符(大小寫+0-9)的索引取得共6個字符;
md5一共4個8位共取4個6位字符,隨便取一個即可作為短鏈。
算法二(有缺陷,長度不受控制,且會出現一個長鏈對多個短鏈)
直接用遞增返回id作為短鏈,短鏈可以有無限多個
算法三(leetcode上面的最優解,覺得不復雜也比較可行)
最優解
public class TinyURL {//用于存儲長鏈接-短鏈接映射private static Map<String, String> longShort = new HashMap();//用于存儲短鏈接-長鏈接映射private static Map<String, String> shortLong = new HashMap();private static String HOST = "www.tinyUrl.com/";// Encodes a URL to a shortened URL.public static String encode(String longUrl) {//如果映射中存在key則直接返回if (longShort.containsKey(longUrl)) {return HOST + longShort.get(longUrl);}//構造短鏈String shortUrl;String chars = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";//碰撞直到沒有重復do {StringBuilder sb = new StringBuilder();for (int i = 0; i < 6; i++) {int n = (int) (Math.random() * chars.length());sb.append(chars.charAt(n));}shortUrl = sb.toString();} while (shortLong.containsKey(shortUrl));//存儲并返回shortLong.put(shortUrl, longUrl);longShort.put(longUrl, shortUrl);return HOST + shortUrl;}// Decodes a shortened URL to its original URL.public static String decode(String shortUrl) {return shortLong.get(shortUrl.replace(HOST, ""));}
}