677. Map Sum Pairs

Medium
Design a map that allows you to do the following:
  • Maps a string key to a given value.
  • Returns the sum of the values that have a key with a prefix equal to a given string.
Implement the MapSum class:
  • MapSum() Initializes the MapSum object.
  • void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
  • int sum(string prefix) Returns the sum of all the pairs' value whose key starts with the prefix.
Example 1:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]
Explanation
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)
Constraints:
  • 1 <= key.length, prefix.length <= 50
  • key and prefix consist of only lowercase English letters.
  • 1 <= val <= 1000
  • At most 50 calls will be made to insert and sum.

解題

加總的時候利用 queue 的技巧。
Runtime: 0 ms, faster than 100%
Memory Usage: 2.9 MB, less than 34.78%
type MapSum struct {
children [26]*MapSum
num int
}
func Constructor() MapSum {
return MapSum{}
}
func (this *MapSum) Insert(key string, val int) {
for i:=0; i<len(key); i++ {
if this.children[key[i] - 'a'] == nil {
this.children[key[i]-'a'] = &MapSum{}
}
this = this.children[key[i] - 'a']
}
this.num = val
}
func (this *MapSum) Sum(prefix string) int {
if prefix == "" {
return 0
}
for i:=0; i<len(prefix); i++ {
if this.children[prefix[i] - 'a'] == nil {
return 0
}
this = this.children[prefix[i] - 'a']
}
queue := make([]*MapSum, 0)
queue = append(queue, this)
res := 0
for len(queue) > 0 {
n := queue[0]
queue = queue[1:]
res += n.num
for i:=0; i<26; i++ {
if n.children[i] != nil {
queue = append(queue, n.children[i])
}
}
}
return res
}
/**
* Your MapSum object will be instantiated and called as such:
* obj := Constructor();
* obj.Insert(key,val);
* param_2 := obj.Sum(prefix);
*/