LeetCode – 535. Encode and Decode TinyURL

題目來源:LeetCode – 535. Encode and Decode 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.

粗略翻譯:

TinyURL是較短的URL

例如將一URLhttps://leetcode.com/problems/design-tinyurl編碼後會變成http://tinyurl.com/4e9iAk的TinyURL

而TinyURLhttp://tinyurl.com/4e9iAk解碼後會還原成https://leetcode.com/problems/design-tinyurl的URL

程式目的為設計此一編碼及解碼的演算法,且並不限制任何的條件,只需要確保URL可以編碼成TinyURL

而TinyURL可以解碼回URL即可。

 


解法:

一開始想到的是直接用Array去儲存所有的URL,並用Array的Length來當作TinyURL的編號

解碼時在根據TinyURL的編號作為Array的index,並取出原來的URL,虛擬碼大約如下所示:

雖然這方法上傳到LeetCode後沒有報錯,也成功解出來,

但不可否認這方法有滿多缺點的,例如:

  1. 同樣的URL如不斷的encode會被編成不同的TinyURL,造成記憶體浪費
  2. 使用者可以藉由TinyURL的編號知道有多少URL被編碼

如不考慮執行時間的話,要解決上述問題我個人是選擇用兩個hashMap去儲存,例如tinyUrlHashMap、urlHashMap

  • tinyUrlHashMap的key為URL,Value為TinyURL
  • urlHashMap的key為TinyURL,Value為URL

將URL編碼前可以先檢查tinyUrlHashMap是否有同樣的key,如果有則直接取出value並return

如果沒有則進行編碼,而編碼的方式可以隨機從[a-z, A-Z, 0-9]等共62的字元中隨機挑選X個,例如挑選6個,這樣一來可以有56,800,235,584種組合,每次編碼完後一樣要檢查tinyUrlHashMap是否有同樣的key,如果有就再一次的重新編碼,直到沒有重複為止。

編碼完成後將要將TinyURL儲存到urlHashMap,之後要將TinyURL解碼回URL,只需要從urlHashMap取出對應的value即可

雖然這方法會有 “因為重複,所以不斷重新編碼” 的情況發生,但是機率實在太低了

何況我們還可以改挑選7個字元,這樣一共會有3,521,614,606,208種組合

那就更不可能重複了

 

不曉得各位高手是否有其他的更佳解?

可以的話希望能指教一下

謝謝。


網站:http://wp.mlab.tw/
GitHub:https://github.com/yoll522/LeetCode
程式碼:https://github.com/yoll522/LeetCode/tree/master/535.%20Encode%20and%20Decode%20TinyURL

95 comments

  1. 륤ȥiphone,륤ȥiPhoneXS,åiphoneXS,åiphone,᥹iphone,ͥiphone ,֥ɥޥۥ, ֥iphone,֥iphoneXSMax,֥iphoneXRͨ؜.LOUIS VUITTON 륤?ȥ iPhone "iPhone X եꥪ" ե M64468 Ʒͬйš. ȥΥiPhoneɤޤؤϴ˚ݤʥեԥ󥯤ȥ륤ȥδĥزĤ˴󵨤Ѻ֎.
    åiphone` http://www.fondsbailletlatour.com

  2. LOUIS VUITTON iPhone Xs֥|iPhone Xsȥ|-֥ɥԩЯiPhone xr,Ʒϥ륤ȥiphone8 ,ͥiphoneX,åiphone7ԩ,᥹iphone8s plusԩ, iphone8ԩ֥,륤ȥ󥳥ԩiphone7/iphone8/iphone8s.֥iphoneԩȫCN륤ȥ󡢥ͥ.֥ɥԩiphone8/iphone8sT.
    륤ȥiphoneXS
    http://www.baptcb.org

  3. \Liphoneiphone7plusiPhonexЩ,եåФäפiPhonex/8/7plusЩALjŮáڥȤʹäؔ!ԩͨ؜,֥ɥѩԩѩԩ֥ͨ؜,iphone7 Щ_j؛С_ѩԩ֥ɼͨ؜,֥ɥԩiphone8 2017Ʒ|iphone8/iphone8 plus֥ɥԩ,iphone7/iphone7 plus֥ɥԩ,ѩԩ,ѩ֥iphoneЯiphone8/ iphone8s plus/iphonex,|˚No.1ѩԩ֥ɌTͨ؜|֥ɥԩͨ؜
    ᥹iphone
    ԩ` http://www.rmllwb.us

  4. iPhone ͨ؜ | iPhone23xˮ?m?nĤʤ餳-֥iphone ԩѩԩ֥ƷϺuͨ؜!֥ɥԩͨ؜n!֥iphoneԩȫCN륤ȥ󡢥ͥ롢å,iphone Щ ֥,iphoneЩ ڳ,Ʒ ˤϥͥ륳ԩiphoneX/XSåԩiphoneX/XS iphone8֥ɥԩ,iphone8ץ饹 ... ֥iphoneXSMax,륤ȥiPhoneXSMax,åiphoneXSMax,᥹iphoneXSMax .
    륤ȥiPhone
    http://www.bcr.at

  5. ԩ֥iphoneXR|iphone XR֥˚|֥iphoneXR |֥iphoneXRЯЩ|֥iphoneXS Maxԩ|֥ ԩiphoneXS|iphoneXS Max֥|֥iphoneXS Max˚| iphoneXS/iphoneXS Max/iphoneXR,iphoneX ֥ɥԩiphone8/iphone8 plusѩԩЯͨ؜, Яiphoneѩԩֱӵ֥꣡ ԩiphoneX/XS֥iphoneXS Max/iphoneXS/iphoneXR.
    åiphone` http://www.grandcanyonbiblio.org

  6. Discover our range of vape pens from all the major e-cig brands at Ave40,Vaping concentrates has become significantly more popular Ave40vapeshopwholesale2019,especially among those that use cannabis for medicinal purposes.Get your vape pen starter kit, try our Positively Fresh e-liquid and sit back and vaporizer.
    digiflavor https://www.ave40.com/brands/digiflavor

  7. The Best Vape Pens for All Types of Vaping 2019-Ave40,Vape Pen Vaporizer Kits | Vape Pens Systems -Ave40vapeshopwholesale2019 Vape Pen Vaporizer Kits are a special starter set featuring a pen-like structure for a user-friendly body chassis. We test all our dab pens to make sure they have a long battery life, good flavor, and are easy to operate.
    wismec vape https://www.ave40.com/brands/wismec

  8. Vape Brands of 2019 | What are the best and most popular vape brands?Ave40vapeshopwholesale2019 What brands are right for you? Find E-Cigarette brands at best price in our vape store.We offer electronic cigarette with best vape brands for wholesale and retail customer.
    vladdin https://www.ave40.com/brands/vladdin

  9. Vape Accessories | Vape Supplies | Vape Case | Vape Craft Inc,We have a wide variety of vape accessories.Ave40vapeshopwholesale2019 From e-cigarette chargers, vape bands, e-cig cases, replacement tanks etc.Vape Accessories for box mods and vape tanks -Ave40,best selection of Vape Accessories & Parts online.
    smoant vape https://www.ave40.com/brands/smoant

  10. Vape Tanks – Vape Mod & Pen Tanks -Ave40vapeshopwholesale2019 Clearomizer is the most well-known atomizer for vaping and very popular for many first-time users.Looking to buy a new clearomizer for your vape? You can find a range of clearomizers from all the top brands here.
    geekvape vape https://www.ave40.com/brands/geekvape

  11. Ave40 | Online Vape Shop | Electronic Cigarettes, E-Juice & More.Ave40vapeshopwholesale2019 Best e-cigarette store for Ireland and England. Try some Best e-liquid and e-cigarette flavors from the best e-cig shop.8000000 Smokers’ choice! Brand electronic cigarettes for vapers, buy best brand e-cigarettes like vapor cigarettes, smokeless cigarettes, vaping starter kit etc.
    smok novo https://www.ave40.com/smok-novo-pod-system-kit.html

  12. Ave40 is your premium e-liquid and cbd brand selling quality products and the best liquids in the vape and cbd industry.Ave40vapeshopwholesale2019 Vape Club | eLiquids | Kits | Mods | Tanks | Pods,The world’s most popular vapor brand. From gettings start kits to ultimate and flavor taste tanks to cloud beast ones, customize your vaping life with SMOK.
    Teslacigs Poker 218w Kit https://www.ave40.com/teslacigs-poker-218-kit-218w-with-resin-tank.html

  13. Shop our range of blu e-cigarette accessories to help you best support your blu experience,Ave40vapeshopwholesale2019 from USB Chargers to e-cigarette batteries & rechargeable devices!E-Cigarette Accessories – Ave40 Shop.Full range of personal vaporizers, e-cigarettes, electronic cigars and e-liquid.
    vape dropshipping https://www.ave40.com/drop-shipping

  14. Vape Kits | Best E-Cigarette and Vaping Kits Online Ave40vapeshopwholesale2019 Ave40,The newest and best e-cigarette starter kits and intermediate vape kits on the e-cig market, over 150 brands of vape kits, e-liquids, accessories & more.if you’re looking for the best vape starter kit, you need to pod it out.
    vaping supply https://www.ave40.com/drop-shipping

  15. Shop eJuice Direct For Your Best Vaping Experience Ave40vapeshopwholesale2019,Ave40 allows you to easily search by desired flavor profile, brand, or nicotine level.Ave40 makes the best vaporizer pen on the market. Offering the best vaporizer pens, portable vaporizers, vaporizer batteries and vaporizer accessories.
    Best Vape Mods 2019 https://www.ave40.com/mods

  16. All the vape brands and manufacturers that Ave40com offers Premium Brand Vape Manufacturer,Ave40vapeshopwholesale2019 We build innovative vape devices including mods, tanks,vaping kits&tools.Best Electronic Cigarettes of 2019 Smok Vaping Products | Smok Box Mods, Vape Coils, & Tanks.
    Vape Atomizer https://www.ave40.com/tanks

  17. VOOPOO Tech aims to develop high-quality vape box mods and starter kits for the electronic cigarette industry.Ave40vapeshopwholesale2019 Popularizes by the DRAG 157W Box Mod.VOOPOO Brand Shop For Sale, Best VOOPOO Vape Device Online Ave40.VooPoo Tech vape products are built with scientific knowledge, intelligence, & advanced innovation in mind.
    Vape Mods For Sale https://www.ave40.com/mods

  18. Make Smoking History – Vapes, E-Cigarettes & Kits from Ave40,Ave40vapeshopwholesale2019 Are you looking for the best offers on e-cigarettes from the world’s most popular vaping brands? If so, click here to shop Ave40 today!Cheap E Cigs | E Cigarettes Online for Sale | Vapes For Sale.
    voopoo vape https://www.ave40.com/brands/voopoo

  19. VAPES E-Cigs, E-juice, Wax Vape Pens, Herbal Vaporizers | Learning how to vape weed is generally easier than learning how to smoke it.Ave40vapeshopwholesale2019 Portable vaporizers are easy to use and fit in your pocket.Ave40 offers you wide selection of portable vaporizers. This kind of vaporizers is perfect for the individual looking for an easy to conceal, on-the-go options.
    Vape Wholesale Supply https://www.ave40.com/wholesale-service.html

  20. Innovation keeps changing the vaping experience!The world’s most popular vapor brand.Ave40vapeshopwholesale2019 From gettings start kits to ultimate and flavor taste tanks to cloud beast ones, customize your vaping life with SMOK.Electronic Cigarettes Wholesale,Vape Wholesale and Distribution – Ave40.
    Cheap Vape Mods https://www.ave40.com/mods

  21. Vaping of Electronic Cigarettes (e cigs ) in Ireland are growing in popularity every day Ave40vapeshopwholesale2019. More and more people are seeking out an online store to find e cigarettes.Buy Electronic E- Cigarette Online India at Best Price | Ave40.com.
    nikola https://www.ave40.com/brands/nikola

  22. Cartomizers & Electronic Cigarettes Refills Online Ave40vapeshopwholesale2019 | Ave40,Find the top rated cartomizers and refill cartridges for e-cigarettes,We are popular with our customers for our wide range of cartomizer options that are compatible with our exclusive vapor cigarettes.
    Clearomizer https://www.ave40.com/tanks

  23. Vapes, E-Liquids & Kits From The Vaping Authority & Original E-Cig Ave40vapeshopwholesale2019 | What is the best vape brand you can buy? Read on to find out our list of the best vape brand in the vaping industry nowadays.Here are the brands that carries top rated vape hardware accessories from Top Vape Brands Ave40.
    Best Vape Mods https://www.ave40.com/mods

  24. Ave40 | Online Vape Shop | Electronic Cigarettes, E-Juice & More.Ave40vapeshopwholesale2019 Best e-cigarette store for Ireland and England. Try some Best e-liquid and e-cigarette flavors from the best e-cig shop.8000000 Smokers’ choice! Brand electronic cigarettes for vapers, buy best brand e-cigarettes like vapor cigarettes, smokeless cigarettes, vaping starter kit etc.
    vaporesso vape https://www.ave40.com/brands/vaporesso

  25. ALL VAPE KITS | Best E-Cigarette Starter Kits -Ave40vapeshopwholesale2019 Ave40 Vape carries a vast amount of the industry’s latest premium vape starter,carrying popular brands such as SMOKTech, Vaporesso and so on.The leading manufacturer of electronic cigarette, Vape, Clearomizer, Tank. Aspire, to be the most respected electronic cigarette brand all over the world.
    dovpo topside squonk mod https://www.ave40.com/dovpo-topside-90w-squonk-mod-10ml.html

  26. Make Smoking History – Vapes, E-Cigarettes & Kits from Ave40,Ave40vapeshopwholesale2019 Are you looking for the best offers on e-cigarettes from the world’s most popular vaping brands? If so, click here to shop Ave40 today!Cheap E Cigs | E Cigarettes Online for Sale | Vapes For Sale.
    smok vape https://www.ave40.com/brands/smoktech

  27. Vape Supplies & Accessories -Ave40,E-Cig Accessories. Need new vape coils? Did you break the glass on your vape tank?Ave40vapeshopwholesale2019 You’ve arrived at the right place.Check out the online vape shop for a huge selection of vape pen accessories plus more!Vape Accessories For Sale | Buy Vaping Accessories at ave40.
    e Cigarette Online https://www.ave40.com/wholesale

  28. Atomizer Tanks for E-Liquid Vape Juice, Clearomizers, Cartomizers,Get quality replacement coils & heads for tanks and atomizers at Ave40.Ave40vapeshopwholesale2019 Vape coils & replacement atomizer heads keep your vape tank fresh and your e-liquids tasting their best. Find replacement coils from Smok & more.
    freemax vape https://www.ave40.com/brands/freemax

  29. Best E-Liquid, E-Cig & Vape Juice Supplies,Ave40 Online Vape Shop- Mods, Tanks, Eliquid & More,Ave40vapeshopwholesale2019 best online vape shop with an impressive collection of authentic vape juice, atomizers, and devices from the top brands like SMOK,Ave40 E-Cig Store | Largest inventory at the lowest prices!
    Wholesale E Cig Starter Kits https://www.ave40.com/starter-kits

  30. Best Vape Pens of 2019 Ave40vapeshopwholesale2019 for E-Liquid, Dry Herb, Wax and Oils,Shop online for e-cigarettes, mods, vape pens, atomizers, dry herb vaporizers, oil/wax pens, enails, ehookah, accessories and USA made e-juice/liquid.Vape Pens | Ave40.com.
    obs vape https://www.ave40.com/brands/obs

  31. Vaping of Electronic Cigarettes (e cigs ) in Ireland are growing in popularity every day Ave40vapeshopwholesale2019. More and more people are seeking out an online store to find e cigarettes.Buy Electronic E- Cigarette Online India at Best Price | Ave40.com.
    vladdin https://www.ave40.com/brands/vladdin

  32. VAPES Sale, Cheap Vape Pens, Discount Vaporizers,Ave40vapeshopwholesale2019 Clearance Mods,Vape mods, advanced kits and box mods from premium brands like Smok and Geek Vape are the all in one option to personalize your vape device.Vape Store & Electronic Cigarette, E-Juice, E-Liquid, and Vaporizer by ave40,We build innovative vape devices including mods, tanks, vaping kits & tools. First rate quality products guaranteed.
    Vaporesso Sky Solo kit https://www.ave40.com/vaporesso-qf-solo-starter-kit-3000mah.html

  33. Ave40| – Premium Vape Brand – Vaping Manufacturer,Are you looking for a new or specific vape juice brand?Ave40vapeshopwholesale2019 Ave40 E Cigs is a leading vape company that prides itself in offering the best electronic cigarettes (e-cigs), e-liquids, vape pens, vape mods and pod mods.
    aspire vape https://www.ave40.com/brands/aspire

  34. Shop our range of blu e-cigarette accessories to help you best support your blu experience,Ave40vapeshopwholesale2019 from USB Chargers to e-cigarette batteries & rechargeable devices!E-Cigarette Accessories – Ave40 Shop.Full range of personal vaporizers, e-cigarettes, electronic cigars and e-liquid.
    joyetech vape https://www.ave40.com/brands/joyetech

  35. Shop our range of blu e-cigarette accessories to help you best support your blu experience,Ave40vapeshopwholesale2019 from USB Chargers to e-cigarette batteries & rechargeable devices!E-Cigarette Accessories – Ave40 Shop.Full range of personal vaporizers, e-cigarettes, electronic cigars and e-liquid.
    Ecig Wholesale China https://www.ave40.com/wholesale

Leave a Reply

你的電子郵件位址並不會被公開。 必要欄位標記為 *