Implement a MapSum class with insert, and sum methods.
For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.
classMapSum{ HashMap<String, Integer> map; TrieNode root; publicMapSum(){ map = new HashMap(); root = new TrieNode(); } publicvoidinsert(String key, int val){ int delta = val - map.getOrDefault(key, 0); map.put(key, val); TrieNode current = root; current.score += delta; for (char c: key.toCharArray()) { current.children.putIfAbsent(c, new TrieNode()); current = current.children.get(c); current.score += delta; } } publicintsum(String prefix){ TrieNode current = root; for (char c: prefix.toCharArray()) { current = current.children.get(c); if (current == null) { return0; } } return current.score; } }
classTrieNode{ Map<Character, TrieNode> children = new HashMap(); int score; }
/** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */