Leetcode - 677 key value mapping (Design)*

Prefix tree + Hashtable

class MapSum {
    
    class TrieNode{
    
        int val = 0;
        TrieNode[] child = new TrieNode[26];
    }
    private TrieNode root;
    private 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 node = root;
       for(char c : key.toCharArray()){
    
           if(node.child[c - 'a'] == null)
               node.child[c - 'a']  = new TrieNode();
             node = node.child[c - 'a'];
             node.val += delta;
       }

    }
    
    public int sum(String prefix) {
    
         TrieNode node = root;
         int sumPrefix = 0;
         for(char c : prefix.toCharArray()){
    
             if(node.child[c - 'a'] == null)
                return 0;
             node = node.child[c - 'a'];
         }
         return node.val;
    }
}

/** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */