LeetCode 677. 键值映射

思路

字典树，边插入边更新sum
代码实现

 1 class MapSum {
 2     class Trie {
 3         public:
 4             bool isWord = false;
 5             int value = 0;
 6             int sum = 0;
 7             Trie* next[26] = {NULL};
 8 
 9             //判断word是否已经存在，返回其对应的value
10             int isExist(const string word) {
11                 Trie* t = this;
12                 for(int i = 0; i < word.length(); ++i){
13                     if(t->next[word[i]-'a'] == NULL) 
14                         return 0;
15                     
16                     t = t->next[word[i]-'a'];
17                 }
18 
19                 if(t->isWord == true)
20                     return t->value;
21                 return 0;
22             }
23 
24             void insert(const string word, int val) {
25                 update(word, isExist(word), val);
26             }
27 
28             void update(const string word, int oldVal, int newVal) {
29                 Trie* t = this;
30                 for(int i = 0; i < word.length(); ++i){
31                     if(t->next[word[i]-'a'] == NULL) {
32                         t->next[word[i]-'a'] = new Trie();
33                     }
34 
35                     t = t->next[word[i]-'a'];
36                     t->sum = t->sum - oldVal + newVal;  
37                 }
38 
39                 t->isWord = true;
40                 t->value = newVal;
41             }
42 
43             int getSum(const string word) {
44                 Trie* t = this;
45                 for(int i = 0; i < word.length(); ++i){
46                     if(t->next[word[i]-'a'] == NULL) {
47                         return 0;
48                     }
49 
50                     t = t->next[word[i]-'a'];
51                 }
52 
53                 return t->sum;
54             }
55 
56 
57     };
58     
59 public:
60     /** Initialize your data structure here. */
61     MapSum() {
62 
63     }
64 
65     Trie* t = new Trie();
66     
67     void insert(string key, int val) {
68         t->insert(key, val);
69     }
70     
71     int sum(string prefix) {
72         return t->getSum(prefix);
73     }
74 };
75 
76 /**
77  * Your MapSum object will be instantiated and called as such:
78  * MapSum* obj = new MapSum();
79  * obj->insert(key,val);
80  * int param_2 = obj->sum(prefix);
81  */