677. Map Sum Pairs #

Problem #

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.

Problem Summary #

Implement a MapSum class that supports two methods, insert and sum:

• MapSum() initializes the MapSum object
• void insert(String key, int val) inserts the key-val key-value pair, where the string represents the key and the integer represents the value val. If the key already exists, the original key-value pair will be replaced with the new key-value pair.
• int sum(string prefix) returns the total sum of the values of all keys that start with the prefix.

Solution Approach #

• Easy problem. Use a map to store the data. The Insert() method stores the key-value pair. The Sum() method accumulates the values corresponding to prefixes that satisfy the condition. To determine whether the condition is satisfied, first judge based on the prefix length; only keys whose length is greater than or equal to the prefix length can possibly satisfy the requirement. If the key has prefix as its prefix, then add this value. Finally, output the total sum.

Code #

package leetcode

type MapSum struct {
	keys map[string]int
}

/** Initialize your data structure here. */
func Constructor() MapSum {
	return MapSum{make(map[string]int)}
}

func (this *MapSum) Insert(key string, val int) {
	this.keys[key] = val
}

func (this *MapSum) Sum(prefix string) int {
	prefixAsRunes, res := []rune(prefix), 0
	for key, val := range this.keys {
		if len(key) >= len(prefix) {
			shouldSum := true
			for i, char := range key {
				if i >= len(prefixAsRunes) {
					break
				}
				if prefixAsRunes[i] != char {
					shouldSum = false
					break
				}
			}
			if shouldSum {
				res += val
			}
		}
	}
	return res
}

/**
 * Your MapSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(key,val);
 * param_2 := obj.Sum(prefix);
 */