Welcome to Subscribe On Youtube

677. Map Sum Pairs

Description

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.

Solutions

  • class Trie { private Trie[] children = new Trie[26]; private int val; public void insert(String w, int x) { Trie node = this; for (int i = 0; i < w.length(); ++i) { int idx = w.charAt(i) - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; node.val += x; } } public int search(String w) { Trie node = this; for (int i = 0; i < w.length(); ++i) { int idx = w.charAt(i) - 'a'; if (node.children[idx] == null) { return 0; } node = node.children[idx]; } return node.val; } } class MapSum { private Map<String, Integer> d = new HashMap<>(); private Trie trie = new Trie(); public MapSum() { } public void insert(String key, int val) { int x = val - d.getOrDefault(key, 0); d.put(key, val); trie.insert(key, x); } public int sum(String prefix) { return trie.search(prefix); } } /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */ 
  • class Trie { public: Trie() : children(26, nullptr) { } void insert(string& w, int x) { Trie* node = this; for (char c : w) { c -= 'a'; if (!node->children[c]) { node->children[c] = new Trie(); } node = node->children[c]; node->val += x; } } int search(string& w) { Trie* node = this; for (char c : w) { c -= 'a'; if (!node->children[c]) { return 0; } node = node->children[c]; } return node->val; } private: vector<Trie*> children; int val = 0; }; class MapSum { public: MapSum() { } void insert(string key, int val) { int x = val - d[key]; d[key] = val; trie->insert(key, x); } int sum(string prefix) { return trie->search(prefix); } private: unordered_map<string, int> d; Trie* trie = new Trie(); }; /** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */ 
  • class Trie: def __init__(self): self.children: List[Trie | None] = [None] * 26 self.val: int = 0 def insert(self, w: str, x: int): node = self for c in w: idx = ord(c) - ord('a') if node.children[idx] is None: node.children[idx] = Trie() node = node.children[idx] node.val += x def search(self, w: str) -> int: node = self for c in w: idx = ord(c) - ord('a') if node.children[idx] is None: return 0 node = node.children[idx] return node.val class MapSum: def __init__(self): self.d = defaultdict(int) self.tree = Trie() def insert(self, key: str, val: int) -> None: x = val - self.d[key] self.d[key] = val self.tree.insert(key, x) def sum(self, prefix: str) -> int: return self.tree.search(prefix) # Your MapSum object will be instantiated and called as such: # obj = MapSum() # obj.insert(key,val) # param_2 = obj.sum(prefix)  
  • type trie struct { children [26]*trie val int } func (t *trie) insert(w string, x int) { for _, c := range w { c -= 'a' if t.children[c] == nil { t.children[c] = &trie{} } t = t.children[c] t.val += x } } func (t *trie) search(w string) int { for _, c := range w { c -= 'a' if t.children[c] == nil { return 0 } t = t.children[c] } return t.val } type MapSum struct { d map[string]int t *trie } func Constructor() MapSum { return MapSum{make(map[string]int), &trie{} } } func (this *MapSum) Insert(key string, val int) { x := val - this.d[key] this.d[key] = val this.t.insert(key, x) } func (this *MapSum) Sum(prefix string) int { return this.t.search(prefix) } /** * Your MapSum object will be instantiated and called as such: * obj := Constructor(); * obj.Insert(key,val); * param_2 := obj.Sum(prefix); */ 
  • class Trie { children: Trie[]; val: number; constructor() { this.children = new Array(26); this.val = 0; } insert(w: string, x: number) { let node: Trie = this; for (const c of w) { const i = c.charCodeAt(0) - 97; if (!node.children[i]) { node.children[i] = new Trie(); } node = node.children[i]; node.val += x; } } search(w: string): number { let node: Trie = this; for (const c of w) { const i = c.charCodeAt(0) - 97; if (!node.children[i]) { return 0; } node = node.children[i]; } return node.val; } } class MapSum { d: Map<string, number>; t: Trie; constructor() { this.d = new Map(); this.t = new Trie(); } insert(key: string, val: number): void { const x = val - (this.d.get(key) ?? 0); this.d.set(key, val); this.t.insert(key, x); } sum(prefix: string): number { return this.t.search(prefix); } } /** * Your MapSum object will be instantiated and called as such: * var obj = new MapSum() * obj.insert(key,val) * var param_2 = obj.sum(prefix) */ 
  • class Trie { constructor() { this.children = new Array(26); this.val = 0; } insert(w, x) { let node = this; for (const c of w) { const i = c.charCodeAt(0) - 97; if (!node.children[i]) { node.children[i] = new Trie(); } node = node.children[i]; node.val += x; } } search(w) { let node = this; for (const c of w) { const i = c.charCodeAt(0) - 97; if (!node.children[i]) { return 0; } node = node.children[i]; } return node.val; } } var MapSum = function () { this.d = new Map(); this.t = new Trie(); }; /** * @param {string} key * @param {number} val * @return {void} */ MapSum.prototype.insert = function (key, val) { const x = val - (this.d.get(key) ?? 0); this.d.set(key, val); this.t.insert(key, x); }; /** * @param {string} prefix * @return {number} */ MapSum.prototype.sum = function (prefix) { return this.t.search(prefix); }; /** * Your MapSum object will be instantiated and called as such: * var obj = new MapSum() * obj.insert(key,val) * var param_2 = obj.sum(prefix) */ 
  • public class Trie { private Trie[] children = new Trie[26]; private int val; public void Insert(string w, int x) { Trie node = this; for (int i = 0; i < w.Length; ++i) { int idx = w[i] - 'a'; if (node.children[idx] == null) { node.children[idx] = new Trie(); } node = node.children[idx]; node.val += x; } } public int Search(string w) { Trie node = this; for (int i = 0; i < w.Length; ++i) { int idx = w[i] - 'a'; if (node.children[idx] == null) { return 0; } node = node.children[idx]; } return node.val; } } public class MapSum { private Dictionary<string, int> d = new Dictionary<string, int>(); private Trie trie = new Trie(); public MapSum() { } public void Insert(string key, int val) { int x = val - (d.ContainsKey(key) ? d[key] : 0); d[key] = val; trie.Insert(key, x); } public int Sum(string prefix) { return trie.Search(prefix); } } /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.Insert(key,val); * int param_2 = obj.Sum(prefix); */ 
  • struct Trie { children: Vec<Option<Box<Trie>>>, val: i32, } impl Trie { fn new() -> Self { Trie { children: (0..26).map(|_| None).collect(), val: 0, } } fn insert(&mut self, w: &str, x: i32) { let mut node = self; for c in w.chars() { let idx = (c as usize) - ('a' as usize); if node.children[idx].is_none() { node.children[idx] = Some(Box::new(Trie::new())); } node = node.children[idx].as_mut().unwrap(); node.val += x; } } fn search(&self, w: &str) -> i32 { let mut node = self; for c in w.chars() { let idx = (c as usize) - ('a' as usize); if node.children[idx].is_none() { return 0; } node = node.children[idx].as_ref().unwrap(); } node.val } } struct MapSum { d: std::collections::HashMap<String, i32>, trie: Trie, } impl MapSum { fn new() -> Self { MapSum { d: std::collections::HashMap::new(), trie: Trie::new(), } } fn insert(&mut self, key: String, val: i32) { let x = val - self.d.get(&key).unwrap_or(&0); self.d.insert(key.clone(), val); self.trie.insert(&key, x); } fn sum(&self, prefix: String) -> i32 { self.trie.search(&prefix) } }

All Problems

All Solutions