677 Map Sum Pairs
677.Map Sum Pairs
1. Question
Implement a MapSum class withinsert
, andsum
methods.
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:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
2. Implementation
(1) Trie
class MapSum {
class TrieNode {
char val;
int sum;
boolean isWord;
TrieNode[] childNode;
public TrieNode(char val, int sum) {
this.val = val;
this.sum = sum;
childNode = new TrieNode[256];
}
}
class Trie {
TrieNode root;
public Trie() {
root = new TrieNode(' ', 0);
}
public void insert(String word, int val, boolean overridden) {
TrieNode curNode = root;
for (char c : word.toCharArray()) {
if (curNode.childNode[c] == null) {
curNode.childNode[c] = new TrieNode(c, val);
}
else {
if (overridden) {
curNode.childNode[c].sum = val;
}
else {
curNode.childNode[c].sum += val;
}
}
curNode = curNode.childNode[c];
}
curNode.isWord = true;
}
public int searchByPrefix(String word) {
TrieNode curNode = root;
if (word == null || word.length() == 0) {
return 0;
}
for (char c : word.toCharArray()) {
if (curNode.childNode[c] == null) {
return 0;
}
curNode = curNode.childNode[c];
}
return curNode.sum;
}
}
Trie trie;
Set<String> set;
/** Initialize your data structure here. */
public MapSum() {
trie = new Trie();
set = new HashSet<>();
}
public void insert(String key, int val) {
trie.insert(key, val, set.contains(key));
set.add(key);
}
public int sum(String prefix) {
return trie.searchByPrefix(prefix);
}
}
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
3. Time & Space Complexity
Trie: insert(): 时间复杂度O(L),L为insert的word的长度, sum(): 时间复杂度O(n),n 为输入的prefix的长度,空间复杂度: O(m), m为插入insert的word的个数
Last updated
Was this helpful?