实现一个 MapSum 类里的两个方法,insert 和 sum。
对于方法 insert,你将得到一对(字符串,整数)的键值对。字符串表示键,整数表示值。如果键已经存在,那么原来的键值对将被替代成新的键值对。
对于方法 sum,你将得到一个表示前缀的字符串,你需要返回所有以该前缀开头的键的值的总和。
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
参考:Trie树
class TrieNode
{
public:
TrieNode *next[26];
int count;
TrieNode():count(0)
{
memset(next,NULL,26*sizeof(TrieNode*));
}
~TrieNode(){}
};
class MapSum {
TrieNode *root;
public:
/** Initialize your data structure here. */
MapSum() {
root = new TrieNode();
}
void insert(string key, int val) {
TrieNode *cur = root;
for(char ch:key)
{
if(cur->next[ch-'a'] == NULL)
cur->next[ch-'a'] = new TrieNode();
cur = cur->next[ch-'a'];
}
cur->count = val;
}
int sum(string prefix) {
TrieNode *cur = root;
for(char ch:prefix)
{
if(cur->next[ch-'a'] == NULL)
return 0;
else
cur = cur->next[ch-'a'];
}
int sumVal = 0;
sumVal += cur->count;
for(int i = 0; i < 26; ++i)
if(cur->next[i])
sumVal += sum(cur->next[i]);
return sumVal;
}
private:
int sum(TrieNode *root)//递归求和
{
int subsum = 0;
if(root == NULL)
return 0;
subsum += root->count;
for(int i = 0; i < 26; ++i)
if(root->next[i])
subsum += sum(root->next[i]);
return subsum;
}
};