题目

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

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

方案一（Huffman编码）

// 为了方便不在进行 int -> hex
type CodecTable struct {
    t    map[string]string
    revT map[string]string
}
func (c CodecTable) Encode(str string) string {
    var b bytes.Buffer
    for i := range str {
        b.WriteString(c.t[string(str[i])])
    }
    return b.String()
}
func (c CodecTable) Decode(str string) string {
    var b bytes.Buffer
    word := ""
    for i := range str {
        word += string(str[i])
        if _, ok := c.revT[word]; ok {
            b.WriteString(c.revT[word])
            word = ""
        }
    }
    return b.String()
}
// Huffman Tree 的一个节点
type HuffNode struct {
    // 使用 string 是为了方便 debug
    value    string
    priority int
    // The index is needed by update and is maintained by the heap.Interface methods.
    index int // The index of the item in the heap.
    left  *HuffNode
    right *HuffNode
}
func (h *HuffNode) GetCodeCTable() *CodecTable {
    t := map[string]string{}
    preOrder(h, []string{}, t)
    revT := map[string]string{}
    for k, v := range t {
        revT[v] = k
    }
    return &CodecTable{
        t:    t,
        revT: revT,
    }
}
func preOrder(h *HuffNode, path []string, t map[string]string) {
    if h == nil {
        return
    }
    path = append(path, "0")
    preOrder(h.left, path, t)
    path = path[:len(path)-1]
    path = append(path, "1")
    preOrder(h.right, path, t)
    path = path[:len(path)-1]
    // 叶子节点
    if h.left == nil && h.right == nil {
        t[h.value] = strings.Join(path, "")
    }
}
type PriorityQueue []*HuffNode
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].priority < pq[j].priority
}
func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
    pq[i].index = i
    pq[j].index = j
}
func (pq *PriorityQueue) Push(x interface{}) {
    n := len(*pq)
    item := x.(*HuffNode)
    item.index = n
    *pq = append(*pq, item)
}
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    old[n-1] = nil  // avoid memory leak
    item.index = -1 // for safety
    *pq = old[0 : n-1]
    return item
}
func BuildHuffmanTree(m map[string]int) *HuffNode {
    pq := make(PriorityQueue, len(m))
    i := 0
    for value, priority := range m {
        pq[i] = &HuffNode{
            value:    value,
            priority: priority,
            index:    i,
        }
        i++
    }
    heap.Init(&pq)
    for pq.Len() > 1 {
        left := heap.Pop(&pq).(*HuffNode)
        right := heap.Pop(&pq).(*HuffNode)
        newNode := &HuffNode{
            left:     left,
            right:    right,
            priority: left.priority + right.priority,
        }
        heap.Push(&pq, newNode)
    }
    root := heap.Pop(&pq).(*HuffNode)
    return root
}
type Codec struct {
    t *CodecTable
}
func Constructor() Codec {
    return Codec{}
}
// Encodes a URL to a shortened URL.
// https://leetcode.com/problems/design-tinyurl
func (this *Codec) encode(longUrl string) string {
    counter := map[string]int{}
    for i := range longUrl {
        counter[string(longUrl[i])]++
    }
    tree := BuildHuffmanTree(counter)
    this.t = tree.GetCodeCTable()
    return this.t.Encode(longUrl)
}
// Decodes a shortened URL to its original URL.
func (this *Codec) decode(shortUrl string) string {
    return this.t.Decode(shortUrl)
}
/**
 * Your Codec object will be instantiated and called as such:
 * obj := Constructor();
 * url := obj.encode(longUrl);
 * ans := obj.decode(url);
 */

使用最小堆（优先级队列）构建 Huffman 树；
前序遍历 Huffman 树，构建转换表；
利用转换表进行编解码。
原文
https://leetcode-cn.com/problems/encode-and-decode-tinyurl/

算法（leetcode）

535. TinyURL 的加密与解密

题目

方案一（Huffman编码）

原文