Leetcode: Encode and Decode TinyURL

By | 2018 年 7 月 19 日

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.

Analysis

Simple question, for speed, just use 2 hash maps one from code to long url, the other reversed from long url to code.

This question can be extended to huge number of urls to be encoded, and should have db storage in real project. And also need consider when capacity get full, the random number may collide a lot.

Notes

  • Regexp usage in ruby
  • securerandom usage

Solutions

Ruby

require 'securerandom'

SHORT_PREFIX = 'http://tinyurl.com/'
REG = Regexp.new(SHORT_PREFIX + '([0-9a-zA-Z]+)')

@code_to_url_map = {}
@url_to_code_map = {}

# Encodes a URL to a shortened URL.
#
# @param {string} longUrl
# @return {string}
def encode(longUrl)
    if code = @url_to_code_map[longUrl]
        return SHORT_PREFIX + code
    end
    5.times do
        code = SecureRandom.uuid[0..5]
        unless @code_to_url_map[code]
            @url_to_code_map[longUrl] = code
            @code_to_url_map[code] = longUrl
            return SHORT_PREFIX + code
        end
    end
    return nil
end

# Decodes a shortened URL to its original URL.
#
# @param {string} shortUrl
# @return {string}
def decode(shortUrl)
    return nil if shortUrl.nil?
    match = shortUrl.match REG
    if match != nil && match.captures.size > 0
        code = match.captures.first
        return @code_to_url_map[code]
    end
    return nil
end

发表评论

电子邮件地址不会被公开。 必填项已用*标注