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
50
calls will be made to insert
and sum
.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);
}