Map Sum Pairs

Design a MapSum class that supports two operations:

• insert(key, val) — Insert the key-value pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
• sum(prefix) — Return the sum of all the values of keys that have a prefix equal to a given prefix.

Implement the MapSum class using a trie data structure.

Examples

Example 1:

Input: operations = ["MapSum","insert","sum","insert","sum"], operands = [[],["apple",3],["ap"],["app",2],["ap"]]

Output: [null,null,3,null,5]

Explanation:

• MapSum() — Initialize the object.
• insert("apple", 3) — Insert key "apple" with val 3.
• sum("ap") — Return 3 (apple = 3).
• insert("app", 2) — Insert key "app" with val 2.
• sum("ap") — Return 5 (apple = 3 + app = 2).

Example 2:

Input: operations = ["MapSum","insert","insert","sum"], operands = [[],["a",3],["a",5],["a"]]

Output: [null,null,null,5]

Explanation: Inserting "a" again with value 5 overrides the previous value of 3.

Constraints

• 1 <= key.length, prefix.length <= 50
• key and prefix consist of only lowercase English letters
• 1 <= val <= 1000
• At most 50 calls will be made to insert and sum