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.