## 677. Map Sum Pairs

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

## Rust Solution

``````use std::collections::hash_map::DefaultHasher;
use std::collections::HashMap;
use std::hash::Hasher;

struct MapSum {
sum: HashMap<u64, i32>,
val: HashMap<u64, i32>,
}

impl MapSum {
fn new() -> Self {
let sum = HashMap::new();
let val = HashMap::new();
MapSum { sum, val }
}

fn insert(&mut self, key: String, val: i32) {
let mut hasher = DefaultHasher::new();
for b in key.bytes() {
hasher.write_u8(b);
let k = hasher.finish();
*self.sum.entry(k).or_default() += val;
}
let k = hasher.finish();
if let Some(prev) = self.val.insert(k, val) {
let mut hasher = DefaultHasher::new();
for b in key.bytes() {
hasher.write_u8(b);
let k = hasher.finish();
*self.sum.entry(k).or_default() -= prev;
}
}
}

fn sum(&mut self, prefix: String) -> i32 {
let mut hasher = DefaultHasher::new();
for b in prefix.bytes() {
hasher.write_u8(b);
}
let k = hasher.finish();
*self.sum.entry(k).or_default()
}
}

#[test]
fn test() {
let mut obj = MapSum::new();
obj.insert("apple".to_string(), 3);
assert_eq!(obj.sum("ap".to_string()), 3);
obj.insert("app".to_string(), 2);
assert_eq!(obj.sum("ap".to_string()), 5);
}
``````

Having problems with this solution? Click here to submit an issue on github.