LeetCode Solutions
677. Map Sum Pairs
Time: Constructor: $O(1)$, insert(key: str, val: int): $O(|\texttt{key}|)$, sum(prefix: str): $O(|\texttt{prefix}|)$ Space: $O(|\texttt{insert(key: str, val: int)})$
struct TrieNode {
vector<shared_ptr<TrieNode>> children;
int sum = 0;
TrieNode() : children(26) {}
};
class MapSum {
public:
void insert(string key, int val) {
const int diff = val - keyToVal[key];
shared_ptr<TrieNode> node = root;
for (const char c : key) {
const int i = c - 'a';
if (node->children[i] == nullptr)
node->children[i] = make_shared<TrieNode>();
node = node->children[i];
node->sum += diff;
}
keyToVal[key] = val;
}
int sum(string prefix) {
shared_ptr<TrieNode> node = root;
for (const char c : prefix) {
const int i = c - 'a';
if (node->children[i] == nullptr)
return 0;
node = node->children[i];
}
return node->sum;
}
private:
shared_ptr<TrieNode> root = make_shared<TrieNode>();
unordered_map<string, int> keyToVal;
};
class TrieNode {
public TrieNode[] children = new TrieNode[26];
public int sum = 0;
}
class MapSum {
public void insert(String key, int val) {
final int diff = val - keyToVal.getOrDefault(key, 0);
TrieNode node = root;
for (final char c : key.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
node.children[i] = new TrieNode();
node = node.children[i];
node.sum += diff;
}
keyToVal.put(key, val);
}
public int sum(String prefix) {
TrieNode node = root;
for (final char c : prefix.toCharArray()) {
final int i = c - 'a';
if (node.children[i] == null)
return 0;
node = node.children[i];
}
return node.sum;
}
private TrieNode root = new TrieNode();
private Map<String, Integer> keyToVal = new HashMap<>();
}
class TrieNode:
def __init__(self):
self.children: Dict[str, TrieNode] = defaultdict(TrieNode)
self.sum = 0
class MapSum:
def __init__(self):
self.root = TrieNode()
self.keyToVal = {}
def insert(self, key: str, val: int) -> None:
diff = val - self.keyToVal.get(key, 0)
node: TrieNode = self.root
for c in key:
if c not in node.children:
node.children[c] = TrieNode()
node = node.children[c]
node.sum += diff
self.keyToVal[key] = val
def sum(self, prefix: str) -> int:
node: TrieNode = self.root
for c in prefix:
if c not in node.children:
return 0
node = node.children[c]
return node.sum