Map Sum Pairs

Medium · trie

A table maps text keys to whole numbers. It starts empty and receives a list of operations. For each position i, operations[i] is either "insert" or "sum", keys[i] is a lowercase word, and values[i] is a number.

"insert" stores keys[i] in the table with the value values[i]. If the key is already in the table, its old value is replaced by the new one (the two are not added together).
"sum" reads the table without changing it. keys[i] is a prefix, and the answer is the total of the values of all keys currently in the table that start with that prefix. A key counts as starting with itself. If no key starts with it, the answer is 0. For a "sum" operation values[i] is 0 and should be ignored.

Return a list with the answer to every "sum" operation, in the order they appear.

Examples

Example 1

Input: operations = ["insert", "sum", "insert", "sum", "insert", "sum"], keys = ["apple", "ap", "app", "ap", "apple", "ap"], values = [3, 0, 2, 0, 5, 0]

Output: [3, 5, 7]

After the first insert only "apple" (3) starts with "ap". Adding "app" (2) makes the total 5. Inserting "apple" again replaces 3 with 5, so the total is 5 + 2 = 7.

Example 2

Input: operations = ["insert", "insert", "sum", "sum"], keys = ["cat", "car", "ca", "dog"], values = [4, -1, 0, 0]

Output: [3, 0]

Both keys start with "ca", so the first answer is 4 + (-1) = 3. No key starts with "dog".

Constraints

1 <= len(operations) <= 10^4
len(keys) == len(values) == len(operations)
operations[i] is "insert" or "sum"
1 <= len(keys[i]) <= 20
keys[i] contains only lowercase English letters
-1000 <= values[i] <= 1000 for an insert, and values[i] == 0 for a sum