# Optimal Java Solution with TrieTree and HashMap

• ``````class MapSum {
/** Initialize your data structure here. */
TrieNode root;
HashMap <String , Integer> hm;

public MapSum() {
root = new TrieNode();
hm = new HashMap<>();
}

public void insert(String key, int val) {
if (hm.containsKey(key)){
int temp = hm.get(key);
hm.put(key , val);
val = val - temp;
} else {
hm.put(key , val);
}

TrieNode current = root;
for (char c : key.toCharArray()){
if (current.children.containsKey(c)){
Pair p = current.children.get(c);
p.value += val;
current.children.put(c , p);
} else {
Pair p = new Pair();
p.value = val;
current.children.put(c,p);
}
current = current.children.get(c).next;
}
}

public int sum(String prefix) {
TrieNode current = root;
int sum = 0;
for (char c: prefix.toCharArray()){
if (!current.children.containsKey(c)){
return 0;
}
sum = current.children.get(c).value;
current = current.children.get(c).next;
}
return sum;
}
}

class TrieNode {
HashMap<Character, Pair> children;

TrieNode() {
children = new HashMap<>();
}
}
class Pair{
int value;
TrieNode next;

Pair(){
value = 0;
next = new TrieNode();
}
}
`````````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.