Implement a MapSum class with insert, and sum methods.
For the method insert, 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 method sum, 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
Intuition and Algorithm
\nFor each key in the map, if that key starts with the given prefix, then add it to the answer.
\n\nComplexity Analysis
\nTime Complexity: Every insert operation is . Every sum operation is where is the number of items in the map, and is the length of the input prefix.
\nSpace Complexity: The space used by map is linear in the size of all input key and val values combined.
Intuition and Algorithm
\nWe can remember the answer for all possible prefixes in a HashMap score. When we get a new (key, val) pair, we update every prefix of key appropriately: each prefix will be changed by delta = val - map[key], where map is the previous associated value of key (zero if undefined.)
Complexity Analysis
\nTime Complexity: Every insert operation is , where is the length of the key, as strings are made of an average length of . Every sum operation is .
\nSpace Complexity: The space used by map and score is linear in the size of all input key and val values combined.
Intuition and Algorithm
\nSince we are dealing with prefixes, a Trie (prefix tree) is a natural data structure to approach this problem. For every node of the trie corresponding to some prefix, we will remember the desired answer (score) and store it at this node. As in Approach #2, this involves modifying each node by delta = val - map[key].
Complexity Analysis
\nTime Complexity: Every insert operation is , where is the length of the key. Every sum operation is .
\nSpace Complexity: The space used is linear in the size of the total input.
\nAnalysis written by: @awice
\n