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);
 */