677. Map Sum Pairs
Tags: ‘Trie’
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.
Example 1:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
Solution
方法1： 首先想到的方法，用Trie稍微修改一下， Node当中存value(默认为0) 12% 100%
class MapSum {
Node root;
private class Node {
private HashMap<Character, Node> children;
private boolean isWord;
private int value;
private Node(int value) {
this.children = new HashMap<Character, Node>();
this.value = value;
}
}
/** Initialize your data structure here. */
public MapSum() {
this.root = new Node(0);
}
public void insert(String key, int val) {
Node p = root;
for (char c: key.toCharArray()) {
p.children.putIfAbsent(c, new Node(0));
p = p.children.get(c);
}
p.isWord = true;
p.value = val;
}
public int sum(String prefix) {
Node p = root;
int sum = 0;
// traverse to end of prefix
for (char c: prefix.toCharArray()) {
if (!p.children.containsKey(c)) {
return 0;
}
p = p.children.get(c);
}
// N-ary tree level order traversal
Queue<Node> queue = new LinkedList<>();
queue.offer(p);
while (!queue.isEmpty()) {
int currentSize = queue.size();
for (int i = 0; i < currentSize; i++) {
Node curr = queue.poll();
if (curr.isWord) sum += curr.value;
if (curr.children.size() > 0) {
for (char c: curr.children.keySet()) {
queue.offer(curr.children.get(c));
}
}
}
}
return sum;
}
}
当然 N-ary tree 的遍历方法还有 Preorder 和 PostOrder
// N-ary tree Preorder traversal
Deque<Node> stack = new LinkedList<>();
stack.push(p);
while(!stack.isEmpty()) {
Node curr = stack.pop();
if (curr.isWord) sum += curr.value;
for (char c: curr.children.keySet()) {
stack.push(curr.children.get(c));
}
}