677 Map Sum Pairs

1. Question

Implement a MapSum class withinsert, andsummethods.
For the methodinsert, 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 methodsum, 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:
1
Input: insert("apple", 3), Output: Null
2
Input: sum("ap"), Output: 3
3
Input: insert("app", 2), Output: Null
4
Input: sum("ap"), Output: 5
Copied!

2. Implementation

(1) Trie
1
class MapSum {
2
class TrieNode {
3
char val;
4
int sum;
5
boolean isWord;
6
TrieNode[] childNode;
7
8
public TrieNode(char val, int sum) {
9
this.val = val;
10
this.sum = sum;
11
childNode = new TrieNode[256];
12
}
13
}
14
15
class Trie {
16
TrieNode root;
17
18
public Trie() {
19
root = new TrieNode(' ', 0);
20
}
21
22
public void insert(String word, int val, boolean overridden) {
23
TrieNode curNode = root;
24
25
for (char c : word.toCharArray()) {
26
if (curNode.childNode[c] == null) {
27
curNode.childNode[c] = new TrieNode(c, val);
28
}
29
else {
30
if (overridden) {
31
curNode.childNode[c].sum = val;
32
}
33
else {
34
curNode.childNode[c].sum += val;
35
}
36
}
37
curNode = curNode.childNode[c];
38
}
39
curNode.isWord = true;
40
}
41
42
public int searchByPrefix(String word) {
43
TrieNode curNode = root;
44
45
if (word == null || word.length() == 0) {
46
return 0;
47
}
48
49
for (char c : word.toCharArray()) {
50
if (curNode.childNode[c] == null) {
51
return 0;
52
}
53
curNode = curNode.childNode[c];
54
}
55
return curNode.sum;
56
}
57
}
58
59
Trie trie;
60
Set<String> set;
61
/** Initialize your data structure here. */
62
public MapSum() {
63
trie = new Trie();
64
set = new HashSet<>();
65
}
66
67
public void insert(String key, int val) {
68
trie.insert(key, val, set.contains(key));
69
set.add(key);
70
}
71
72
public int sum(String prefix) {
73
return trie.searchByPrefix(prefix);
74
}
75
}
76
77
/**
78
* Your MapSum object will be instantiated and called as such:
79
* MapSum obj = new MapSum();
80
* obj.insert(key,val);
81
* int param_2 = obj.sum(prefix);
82
*/
Copied!

3. Time & Space Complexity

Trie: insert(): 时间复杂度O(L),L为insert的word的长度, sum(): 时间复杂度O(n),n 为输入的prefix的长度,空间复杂度: O(m), m为插入insert的word的个数