Implement a MapSum class with insert, and sum methods.
For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.
Example 1:
Input: insert(“apple”, 3), Output: Null
Input: sum(“ap”), Output: 3
Input: insert(“app”, 2), Output: Null
Input: sum(“ap”), Output: 5
hashtable 一个存单词表 一个存前缀表1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class MapSum {
public:
/** Initialize your data structure here. */
MapSum() {
}
void insert(string key, int val) {
if(vals.count(key)) val-=vals[key];
vals[key]=val;
for(int i=1;i<=key.length();i++){
string t=key.substr(0,i);
pre[t]+=val;
}
}
int sum(string prefix) {
return pre[prefix];
}
unordered_map<string,int> vals;
unordered_map<string,int> pre;
};
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/