## 677. Map Sum Pairs

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
```

b'
\n\n

#### Approach #1: Brute Force [Accepted]

\n

Intuition and Algorithm

\n

For each key in the map, if that key starts with the given prefix, then add it to the answer.

\n\n

Complexity Analysis

\n
\n
• \n

Time 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.

\n
• \n
• \n

Space Complexity: The space used by `map` is linear in the size of all input `key` and `val` values combined.

\n
• \n
\n
\n

#### Approach #2: Prefix Hashmap [Accepted]

\n

Intuition and Algorithm

\n

We 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.)

\n\n

Complexity Analysis

\n
\n
• \n

Time 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 .

\n
• \n
• \n

Space Complexity: The space used by `map` and `score` is linear in the size of all input `key` and `val` values combined.

\n
• \n
\n
\n

#### Approach #3: Trie [Accepted]

\n

Intuition and Algorithm

\n

Since 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]`.

\n\n

Complexity Analysis

\n
\n
• \n

Time Complexity: Every insert operation is , where is the length of the key. Every sum operation is .

\n
• \n
• \n

Space Complexity: The space used is linear in the size of the total input.

\n
• \n
\n
\n

Analysis written by: @awice

\n
'