# 【进阶篇 - Day 42】 2020-12-12 - 677. 键盘映射（02.Trie ）
# 题目描述
# 入选理由
1.上一次大家实现了 trie，这次可用上次实现的 trie 做点应用
# 题目描述
实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。
示例 1:
输入: insert("apple", 3), 输出: Null 输入: sum("ap"), 输出: 3 输入: insert("app", 2), 输出: Null 输入: sum("ap"), 输出: 5
来源：力扣（LeetCode） 链接：leetcode-cn.com/problems/map-sum-pairs 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
# 我的回答
# 解法一
# 时空复杂度
时间复杂度：O(n)
空间复杂度: O(1)