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.
classTrie:def__init__(self):self.children:List[Trie|None]=[None]*26self.val:int=0definsert(self,w:str,x:int):node=selfforcinw:idx=ord(c)-ord('a')ifnode.children[idx]isNone:node.children[idx]=Trie()node=node.children[idx]node.val+=xdefsearch(self,w:str)->int:node=selfforcinw:idx=ord(c)-ord('a')ifnode.children[idx]isNone:return0node=node.children[idx]returnnode.valclassMapSum:def__init__(self):self.d=defaultdict(int)self.tree=Trie()definsert(self,key:str,val:int)->None:x=val-self.d[key]self.d[key]=valself.tree.insert(key,x)defsum(self,prefix:str)->int:returnself.tree.search(prefix)# Your MapSum object will be instantiated and called as such:# obj = MapSum()# obj.insert(key,val)# param_2 = obj.sum(prefix)
classTrie{privateTrie[]children=newTrie[26];privateintval;publicvoidinsert(Stringw,intx){Trienode=this;for(inti=0;i<w.length();++i){intidx=w.charAt(i)-'a';if(node.children[idx]==null){node.children[idx]=newTrie();}node=node.children[idx];node.val+=x;}}publicintsearch(Stringw){Trienode=this;for(inti=0;i<w.length();++i){intidx=w.charAt(i)-'a';if(node.children[idx]==null){return0;}node=node.children[idx];}returnnode.val;}}classMapSum{privateMap<String,Integer>d=newHashMap<>();privateTrietrie=newTrie();publicMapSum(){}publicvoidinsert(Stringkey,intval){intx=val-d.getOrDefault(key,0);d.put(key,val);trie.insert(key,x);}publicintsum(Stringprefix){returntrie.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); */
classTrie{public:Trie():children(26,nullptr){}voidinsert(string&w,intx){Trie*node=this;for(charc:w){c-='a';if(!node->children[c]){node->children[c]=newTrie();}node=node->children[c];node->val+=x;}}intsearch(string&w){Trie*node=this;for(charc:w){c-='a';if(!node->children[c]){return0;}node=node->children[c];}returnnode->val;}private:vector<Trie*>children;intval=0;};classMapSum{public:MapSum(){}voidinsert(stringkey,intval){intx=val-d[key];d[key]=val;trie->insert(key,x);}intsum(stringprefix){returntrie->search(prefix);}private:unordered_map<string,int>d;Trie*trie=newTrie();};/** * Your MapSum object will be instantiated and called as such: * MapSum* obj = new MapSum(); * obj->insert(key,val); * int param_2 = obj->sum(prefix); */
typetriestruct{children[26]*trievalint}func(t*trie)insert(wstring,xint){for_,c:=rangew{c-='a'ift.children[c]==nil{t.children[c]=&trie{}}t=t.children[c]t.val+=x}}func(t*trie)search(wstring)int{for_,c:=rangew{c-='a'ift.children[c]==nil{return0}t=t.children[c]}returnt.val}typeMapSumstruct{dmap[string]intt*trie}funcConstructor()MapSum{returnMapSum{make(map[string]int),&trie{}}}func(this*MapSum)Insert(keystring,valint){x:=val-this.d[key]this.d[key]=valthis.t.insert(key,x)}func(this*MapSum)Sum(prefixstring)int{returnthis.t.search(prefix)}/** * Your MapSum object will be instantiated and called as such: * obj := Constructor(); * obj.Insert(key,val); * param_2 := obj.Sum(prefix); */
classTrie{children:Trie[];val:number;constructor(){this.children=newArray(26);this.val=0;}insert(w:string,x:number){letnode:Trie=this;for(constcofw){consti=c.charCodeAt(0)-97;if(!node.children[i]){node.children[i]=newTrie();}node=node.children[i];node.val+=x;}}search(w:string):number{letnode:Trie=this;for(constcofw){consti=c.charCodeAt(0)-97;if(!node.children[i]){return0;}node=node.children[i];}returnnode.val;}}classMapSum{d:Map<string,number>;t:Trie;constructor(){this.d=newMap();this.t=newTrie();}insert(key:string,val:number):void{constx=val-(this.d.get(key)??0);this.d.set(key,val);this.t.insert(key,x);}sum(prefix:string):number{returnthis.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) */