Lt677. 键值映射

677. 键值映射

实现一个 MapSum 类，支持两个方法，insert 和 sum：

• MapSum() 初始化 MapSum 对象
• void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
• int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

​

示例：
输入： [“MapSum”, “insert”, “sum”, “insert”, “sum”] [[], [“apple”, 3], [“ap”], [“app”, 2], [“ap”]] 输出： [null, null, 3, null, 5] 解释： MapSum mapSum = new MapSum(); mapSum.insert(“apple”, 3); mapSum.sum(“ap”); // return 3 (apple = 3) mapSum.insert(“app”, 2); mapSum.sum(“ap”); // return 5 (apple + app = 3 + 2 = 5)
​

提示：

• 1 <= key.length, prefix.length <= 50
• key 和 prefix 仅由小写英文字母组成
• 1 <= val <= 1000
• 最多调用 50 次 insert 和 sum

思路

构建一个类树结构，哈希表记录前缀和对应 val 值，insert 时更新对应树，sum 时，visit 到对应节点，对 val 中值求和返回即可。

解答

var MapSum = function () {
  this.map = {};
};

/**
 * @param {string} key
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function (key, val) {
  const arr = key.split("");
  let cur = this.map;
  while (arr.length) {
    const char = arr.shift();
    if (!cur[char]) cur[char] = { val: { [key]: val }, child: {} };
    else cur[char].val[key] = val;
    cur = cur[char].child;
  }
  cur.val = val;
};

/**
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
  const arr = prefix.split("");
  let cur = this.map,
    res = 0;
  while (arr.length) {
    const char = arr.shift();
    if (!cur[char]) return 0;
    res = Object.values(cur[char].val).reduce((a, b) => +a + +b);
    cur = cur[char].child;
  }
  return res;
};