0677. Map Sum Pairs
https://leetcode.com/problems/map-sum-pairs
Description
Design a map that allows you to do the following:
Maps a string key to a given value.
Returns the sum of the values that have a key with a prefix equal to a given string.
Implement the MapSum
class:
MapSum()
Initializes theMapSum
object.void insert(String key, int val)
Inserts thekey-val
pair into the map. If thekey
already existed, the originalkey-value
pair will be overridden to the new one.int sum(string prefix)
Returns the sum of all the pairs' value whosekey
starts with theprefix
.
Example 1:
**Input**
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
**Output**
[null, null, 3, null, 5]
**Explanation**
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
Constraints:
1 <= key.length, prefix.length <= 50
key
andprefix
consist of only lowercase English letters.1 <= val <= 1000
At most
50
calls will be made toinsert
andsum
.
ac
class MapSum {
TrieNode root;
Map<String, Integer> map;
/** Initialize your data structure here. */
public MapSum() {
root = new TrieNode();
map = new HashMap<>();
}
public void insert(String key, int val) {
int diff = val - map.getOrDefault(key, 0);
map.put(key, val);
add(key, diff);
}
private void add(String key, int diff) {
TrieNode r = root;
for (int i = 0; i < key.length(); i++) {
int pos = key.charAt(i) - 'a';
if (r.next[pos] == null) r.next[pos] = new TrieNode();
r = r.next[pos];
r.sum += diff;
}
}
public int sum(String prefix) {
TrieNode r = root;
for (int i = 0; i < prefix.length(); i++) {
int pos = prefix.charAt(i) - 'a';
if (r.next[pos] == null) return 0;
r = r.next[pos];
}
return r.sum;
}
}
class TrieNode {
TrieNode[] next = new TrieNode[26];
int sum = 0;
}
/**
* Your MapSum object will be instantiated and called as such:
* MapSum obj = new MapSum();
* obj.insert(key,val);
* int param_2 = obj.sum(prefix);
*/
Last updated
Was this helpful?