# 0677. Map Sum Pairs
###### tags: `Leetcode` `Medium` `Trie`
Link: https://leetcode.com/problems/map-sum-pairs/
## 思路
典型Trie
唯一要注意的是如果这个string之前出现过了 现在的值要覆盖掉原来的值
## Code

class MapSum {
    TrieNode root;
    Map<String, Integer> map;
    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }
    
    public void insert(String key, int val) {
        int delta = val-map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode curr = root;
        curr.score += delta;
        for(char c:key.toCharArray()){
            if(curr.children[c-'a']==null) curr.children[c-'a']=new TrieNode();
            curr = curr.children[c-'a'];
            curr.score += delta;
        }
    }
    
    public int sum(String prefix) {
        TrieNode curr = root;
        for(char c:prefix.toCharArray()){
            curr = curr.children[c-'a'];
            if(curr==null) return 0;
        }
        return curr.score;
    }
}
class TrieNode{
    TrieNode[] children = new TrieNode[26];
    int score = 0;
}