Solution: Map Sum Pairs
Discover how to design a MapSum class that supports inserting key-value pairs and returning the sum of all values with a given prefix. Understand how to leverage tries to optimize prefix queries and handle updates efficiently by tracking the difference between new and old values. This lesson helps you implement and reason about an effective solution for prefix sum problems using trie data structures.
We'll cover the following...
Statement
Design a data structure that supports the following operations:
Insert a key-value pair:
Each key is a string, and each value is an integer.
If the key already exists, update its value to (overriding the previous value).
Return the prefix sum:
Given a string,
prefix, return the total sum of all values associated with keys that start with this prefix.
To accomplish this, implement a class MapSum:
Constructor: Initializes the object.
void insert (String key, int val): Inserts the key-value pair into the data structure. If the key already exists, its value is updated to the new one.
int sum (String prefix): Returns the total sum of values for all keys that begin with the specified prefix.
Constraints:
key.length,prefix.length...