题目描述

TinyURL 是一种 URL 简化服务，比如：当你输入一个 URL https://leetcode.com/problems/design-tinyurl 时，它将返回一个简化的 URL http://tinyurl.com/4e9iAk。

要求：设计一个 TinyURL 的加密 encode 和解密 decode 的方法。你的加密和解密算法如何设计和运作是没有限制的，你只需要保证一个 URL 可以被加密成一个 TinyURL，并且这个 TinyURL 可以用解密方法恢复成原本的 URL。

算法

(哈希表) $O(1)$

1. 直接用计数器递增的方式哈希一个给定 URL。将这个 URL 映射到一个递增的计数值上，用当前计数值生产一个 TinyURL，同时记录下当前计数值对应的 URL。
2. 解码时，直接从记录中取出当前计数值对应的 URL。

时间复杂度

• 编码和解码都是常数时间复杂度。

空间复杂度

• 需要 $O(n)$ 的额外空间记录所有的 URL。

Go 代码

type Codec struct {
    seen    map[string]int
    record  map[int]string
    counter int
}

func Constructor() Codec {
    return Codec{
        seen:    make(map[string]int),
        record:  make(map[int]string),
        counter: 0,
    }
}

// Encodes a URL to a shortened URL.
func (this *Codec) encode(longUrl string) string {
    v, ok := this.seen[longUrl]
    if ok {
        return fmt.Sprintf("http://tinyurl.com/%d", v)
    }
    this.counter++
    this.seen[longUrl] = this.counter
    this.record[this.counter] = longUrl
    return fmt.Sprintf("http://tinyurl.com/%d", this.counter)
}

// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
    v := 0
    fmt.Sscanf(shortUrl, "http://tinyurl.com/%d", &v)
    return this.record[v]
}

/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * url := obj.encode(longUrl);
 * ans := obj.decode(url);
 */