# Leetcode 677 - Map sum pairs

Note:

• Use Tire data structure.
• Use {} instead of Map to store letters.
• Need a DFS helpe to search chars.
• When i <= prefix.length - 1, only continue saerch on key === prefix[i].
• When i >= prefix.length, do normal DFS.
• Only add val on two situations:
• i === prefix.length - 1 && val is defined.
• i >= prefix.length && val is defined.

Question:

Design a map that allows you to do the following:

• Maps a string key to a given value.
• Returns the sum of the values that have a key with a prefix equal to a given string.

Implement the MapSum class:

• MapSum() Initializes the MapSum object.
• void insert(String key, int val) Inserts the key-val pair into the map. If the key already existed, the original key-value pair will be overridden to the new one.
• int sum(string prefix) Returns the sum of all the pairs’ value whose key starts with the prefix.

Example:

Code: