## Algorithm

Problem Name: 677. Map Sum Pairs

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`.

## Code Examples

### #1 Code Example with C++ Programming

```Code - C++ Programming```

``````
class MapSum {
struct TrieNode{
int sum;
TrieNode* next[26];
TrieNode(): sum(0){
memset(next, NULL, sizeof(next));
}
};

unordered_mapm;
TrieNode* root;

public:
/** Initialize your data structure here. */
MapSum() {
root = new TrieNode();
}

void insert(string key, int val) {
bool replace = false;
if(m.count(key)) replace = true;
TrieNode* p = root;
for(char c: key){
if(!p->next[c - 'a']) p->next[c - 'a'] = new TrieNode();
p = p->next[c - 'a'];
p->sum += replace ? val - m[key] : val;
}
m[key] = val;
}

int sum(string prefix) {
TrieNode* p = root;
for(char c: prefix){
if(!p->next[c - 'a']) return 0;
p = p->next[c - 'a'];
}
return p->sum;
}
};
``````
Copy The Code &

Input

cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

cmd
[null, null, 3, null, 5]

### #2 Code Example with Java Programming

```Code - Java Programming```

``````
class MapSum {

/** Initialize your data structure here. */
TrieNode root;
Map map;
public MapSum() {
root = new TrieNode('-');
map = new HashMap<>();
}

public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
TrieNode curr = root;
for (int i = 0; i < key.length(); i++) {
if (!curr.map.containsKey(key.charAt(i))) {
curr.map.put(key.charAt(i), new TrieNode(key.charAt(i)));
}
curr = curr.map.get(key.charAt(i));
curr.score += delta;
}
}

public int sum(String prefix) {
TrieNode curr = root;
for (int i = 0; i < prefix.length(); i++) {
if (!curr.map.containsKey(prefix.charAt(i))) {
return 0;
}
curr = curr.map.get(prefix.charAt(i));
}
return curr.score;
}
}

class TrieNode {
char c;
Map map;
int score;

public TrieNode(char c) {
this.c = c;
map = new HashMap<>();
score = 0;
}
}
``````
Copy The Code &

Input

cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

cmd
[null, null, 3, null, 5]

### #3 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const MapSum = function() {
this.hash = {};
};

MapSum.prototype.insert = function(key, val) {
this.hash[key] = val;
};

MapSum.prototype.sum = function(prefix) {
let res = 0;
Object.keys(this.hash).forEach(el => {
if (el.indexOf(prefix) === 0) {
res += this.hash[el];
}
});
return res;
};
``````
Copy The Code &

Input

cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

cmd
[null, null, 3, null, 5]

### #4 Code Example with Python Programming

```Code - Python Programming```

``````
class MapSum:

def __init__(self):
"""
"""
from collections import defaultdict
self.dic = defaultdict(int)

def insert(self, key, val):
"""
:type key: str
:type val: int
:rtype: void
"""
self.dic[key] = val

def sum(self, prefix):
"""
:type prefix: str
:rtype: int
"""
sm = 0
for k in self.dic:
if k[:len(prefix)] == prefix: sm += self.dic[k]
return sm

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
``````
Copy The Code &

Input

cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

cmd
[null, null, 3, null, 5]