677. 键值映射
实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5
class MapSum {
class TrieNode{
TrieNode[] children;
int count;
public TrieNode(){
this.children = new TrieNode[26];
count=0;
}
}
TrieNode root;
public MapSum() {
root = new TrieNode();
}
public void insert(String key, int val) {
TrieNode cur = root;
for(char c:key.toCharArray()){
if(cur.children[c-'a']==null){
cur.children[c-'a'] = new TrieNode();
}
cur = cur.children[c-'a'];
}
cur.count=val;
}
public int sum(String prefix) {
TrieNode cur = root;
int res=0;
for(char c:prefix.toCharArray()){
if(cur.children[c-'a']==null)
return 0;
cur = cur.children[c-'a'];
}
res=getSum(cur);
return res;
}
public int getSum(TrieNode root){
int res=root.count;
for(int i=0;i<26;i++){
if(root.children[i]!=null){
res+=getSum(root.children[i]);
}
}
return res;
}
}
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/