題目

實現一個 MapSum 類，支援兩個方法，insert 和 sum：

MapSum() 初始化 MapSum 物件

void insert(String key, int val) 插入 key-val 鍵值對，字串表示鍵 key ，整數表示值 val 。

如果鍵 key 已經存在，那麼原來的鍵值對將被替代成新的鍵值對。

int sum(string prefix) 返回所有以該字首 prefix 開頭的鍵 key 的值的總和。

示例：輸入： ["MapSum", "insert", "sum", "insert", "sum"]

[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

輸出：[null, null, 3, null, 5]

解釋： MapSum mapSum = new MapSum();

mapSum.insert("apple", 3);

mapSum.sum("ap"); // return 3 (apple = 3)

mapSum.insert("app", 2);

mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)

提示：1 <= key.length, prefix.length <= 50

key 和 prefix 僅由小寫英文字母組成

1 <= val <= 1000

最多呼叫 50 次 insert 和 sum

解題思路分析

1、trie樹；時間複雜度O(n)，空間複雜度O(n)

type MapSum struct {	val  int	next map[int32]*MapSum}func Constructor() MapSum {	return MapSum{		val:  0,		next: make(map[int32]*MapSum),	}}func (this *MapSum) Insert(key string, val int) {	node := this	for _, v := range key {		if _, ok := node.next[v]; ok == false {			temp := Constructor()			node.next[v] = &temp		}		node = node.next[v]	}	node.val = val}func (this *MapSum) Sum(prefix string) int {	node := this	for _, v := range prefix {		if _, ok := node.next[v]; ok == false {			return 0		}		node = node.next[v]	}	res := 0	queue := make([]*MapSum, 0)	queue = append(queue, node)	for len(queue) > 0 {		temp := queue[0]		queue = queue[1:]		res = res + temp.val		for _, v := range temp.next {			queue = append(queue, v)		}	}	return res}

2、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

type MapSum struct {	m    map[string]int	data map[string]map[string]bool}func Constructor() MapSum {	return MapSum{		m:    make(map[string]int),		data: make(map[string]map[string]bool),	}}func (this *MapSum) Insert(key string, val int) {	this.m[key] = val	for i := 1; i <= len(key); i++ {		str := key[:i]		if _, ok := this.data[str]; ok == false {			this.data[str] = make(map[string]bool)		}		this.data[str][key] = true	}}func (this *MapSum) Sum(prefix string) int {	res := 0	for key := range this.data[prefix] {		res = res + this.m[key]	}	return res}

3、雜湊輔助；時間複雜度O(n)，空間複雜度O(n)

type MapSum struct {	m map[string]int}func Constructor() MapSum {	return MapSum{		m: make(map[string]int),	}}func (this *MapSum) Insert(key string, val int) {	this.m[key] = val}func (this *MapSum) Sum(prefix string) int {	res := 0	for key, value := range this.m {		if strings.HasPrefix(key, prefix) {			res = res + value		}	}	return res}

總結

Medium題目，設計題，可以使用trie樹