Leetcode Problem 677: Map Sum Pairs
Implement the MapSum
class that supports two operations:
void insert(string key, int val)
: Inserts the key-value pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.int sum(string prefix)
: Returns the sum of all the pairs’ values whose keys start with the given prefix.To efficiently support both operations, we will use a combination of a HashMap and a Trie (prefix tree):
#include <unordered_map>
#include <string>
using namespace std;
class TrieNode {
public:
int valueSum;
unordered_map<char, TrieNode*> children;
TrieNode() : valueSum(0) {}
};
class MapSum {
private:
TrieNode* root;
unordered_map<string, int> keyValueMap;
public:
/** Initialize your data structure here. */
MapSum() {
root = new TrieNode();
}
void insert(string key, int val) {
int delta = val;
if (keyValueMap.find(key) != keyValueMap.end()) {
delta -= keyValueMap[key];
}
keyValueMap[key] = val;
TrieNode* node = root;
for (char c : key) {
if (node->children.find(c) == node->children.end()) {
node->children[c] = new TrieNode();
}
node = node->children[c];
node->valueSum += delta;
}
}
int sum(string prefix) {
TrieNode* node = root;
for (char c : prefix) {
if (node->children.find(c) == node->children.end()) {
return 0;
}
node = node->children[c];
}
return node->valueSum;
}
};
valueSum
by the delta at each node corresponding to characters of the key.valueSum
at the final node which represents the sum of all values of keys sharing the given prefix.Got blindsided by a question you didn’t expect?
Spend too much time studying?
Or simply don’t have the time to go over all 3000 questions?