LeetCode #677 Map Sum Pairs

Medium

Problem

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

Solution

Use a trie to save each string, and use a map in trie for recording value of each string. Once there is a string be inserted into this trie, update the delta value which is inserted value — current value in nodes on the updating path.

Complexity

Both insert and sum need to iterate entire given string, so their time complexity are both O(k) if k denotes to the length of the given string.