C++刷leetcode（677. 键值映射）【字典树】

糖逗

题目描述:

1. 实现一个 MapSum 类里的两个方法，insert 和 sum。
   
2. 
   
3. 对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
   
4. 
   
5. 对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
   
6. 
   
7. 示例 1:
   
8. 
   
9. 输入: insert("apple", 3), 输出: Null
   
10. 输入: sum("ap"), 输出: 3
    
11. 输入: insert("app", 2), 输出: Null
    
12. 输入: sum("ap"), 输出: 5
    
13. 
    
14. 来源：力扣（LeetCode）
    
15. 链接：https://leetcode-cn.com/problems/map-sum-pairs
    
16. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

1. class MapSum {
   
2. private:
   
3.     bool isEnd;
   
4.     MapSum* next[26];
   
5.     vector<int> value;
   
6.     set<string> store;
   
7. public:
   
8.     /** Initialize your data structure here. */
   
9.     MapSum() {
   
10.         isEnd = false;
    
11.         memset(next, 0, sizeof(next));
    
12.         value = {};
    
13.     }
    
14.    
    
15.     void insert(string key, int val) {
    
16.         MapSum* node = this;
    
17.         auto cha = store.insert(key);
    
18.         bool flag = cha.second;
    
19.         for(auto cha : key){
    
20.             if(node -> next[cha - 'a'] == NULL){
    
21.                 node -> next[cha - 'a'] = new MapSum();
    
22.             }
    
23.             node = node -> next[cha - 'a'];
    
24.             if(flag == false)node -> value.pop_back();
    
25.             node ->value.push_back(val);
    
26.         }
    
27.         node -> isEnd = true;
    
28.     }
    
29.    
    
30.     int sum(string prefix) {
    
31.         MapSum*node = this;
    
32.         int res = 0;
    
33.         for(auto cha : prefix){
    
34.             if(node -> next[cha - 'a'] == NULL) return res;
    
35.             node = node -> next[cha - 'a'];
    
36.         }
    
37.         int len = node -> value.size();
    
38.         for(int i = 0; i < len; i++){
    
39.             res += node -> value[i];
    
40.         }
    
41.         return res;
    
42.     }
    
43. };
    
44. 
    
45. /**
    
46. * Your MapSum object will be instantiated and called as such:
    
47. * MapSum* obj = new MapSum();
    
48. * obj->insert(key,val);
    
49. * int param_2 = obj->sum(prefix);
    
50. */

复制代码