问题入口
通过递归很好解决该问题，但是由于遍历次数过多引发了Runtime Error（ps：这是用C语言编写的情况下），所以需要寻找其他解决方法。
在我原本使用递归思路解决问题时，我对MapSum结构体定义如下：
struct MapSum{ MapSum **next; int value; };
value>0（题目给的值都是正数）就表达了这个单词的值 ，同时也说明这是单词的结尾。等于一个属性参与了两个动作。
如果我把每次加入的值都加在每一个字母上又会如何呢？
例如，进行如下操作
Input: insert("apple", 3), Output: Null Input: sum("ap"), Output: 3 Input: insert("app", 2), Output: Null Input: sum("ap"), Output: 5
可以看到第二次加入的app，对应的三个字母的值都是5。这样sum操作就仅是通过for循环到达第二个p的位置 ，返回value即可。
然而如果是更新操作，值会叠加，不会更新。
Input: insert("apple", 3), Output: Null Input: sum("ap"), Output: 3 Input: insert("apple", 2), Output: Null Input: sum("ap"), Output: 5 // incorrect, the answer is 2对于更新操作，我们需要再遍历一次Tire树减去之前的value ——即添加后的value-形参value。另外，结构体MapSum需要添加一个属性bool isWord。因为此时的value是用来表现包含这个字母的值的总和，它不具备判断是否是一个单词的语义。而isWord可以判断是进行添加操作还是更新操作。如果isWord为true，证明这是更新操作，我们需要减去之前的value；如果isWord为false, 证明这是增加操作。
#define LEN 26
typedef struct MapSum MapSum; struct MapSum{ MapSum **next; int value; bool isWord; };
/** Initialize your data structure here. */
MapSum* mapSumCreate() { MapSum *ms = malloc(sizeof(MapSum)); int space = sizeof(MapSum*)*LEN; ms->next = malloc(space); memset(ms->next,0,space); ms->value = 0; ms->isWord=false; return ms; }
void updateValue(MapSum* obj, char *key,int val){ for(int i=0;key[i]!='\0';i++){ int nIndex=key[i]-'a'; obj=obj->next[nIndex]; obj->value+=val; } }
void mapSumInsert(MapSum* obj, char * key, int val) { MapSum *root = obj; for(int i=0;key[i]!='\0';i++){ int nIndex = key[i]-'a'; if(!(obj->next[nIndex])) obj->next[nIndex]=mapSumCreate(); obj=obj->next[nIndex]; obj->value+=val; } if(obj->isWord) updateValue(root,key,-1*(obj->value-val)); obj->isWord=true; }
int mapSumSum(MapSum* obj, char * prefix) { for(int i=0;prefix[i]!='\0';i++){ int nIndex = prefix[i]-'a'; if(obj->next[nIndex]) obj=obj->next[prefix[i]-'a']; else return NULL; } return obj->value; }
void mapSumFree(MapSum* obj) { free(obj->next); free(obj); }
/** * Your MapSum struct will be instantiated and called as such: * MapSum* obj = mapSumCreate(); * mapSumInsert(obj, key, val); * int param_2 = mapSumSum(obj, prefix); * mapSumFree(obj); */
最后来分析一下时间复杂度。假设添加的单词有n个字符，查找的前缀有k个字符。那么增加操作的时间复杂度为O(n)，查找操作的时间复杂度为O(k)
