Approach #1: Brute Force [Accepted]
Intuition and Algorithm
For each key in the map, if that key starts with the given prefix, then add it to the answer.
Complexity Analysis

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.

Space Complexity: The space used by
map
is linear in the size of all inputkey
andval
values combined.
Approach #2: Prefix Hashmap [Accepted]
Intuition and Algorithm
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.)
Complexity Analysis

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 .

Space Complexity: The space used by
map
andscore
is linear in the size of all inputkey
andval
values combined.
Approach #3: Trie [Accepted]
Intuition and Algorithm
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]
.
Complexity Analysis

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

Space Complexity: The space used is linear in the size of the total input.
Analysis written by: @awice