677. 键值映射

方法一：Trie

字符串前缀的处理可以使用 Trie（前缀树）来进行处理：

class TrieNode {
  value = 0
  next = new Map<string, TrieNode>()
}
class MapSum {
  root: TrieNode
  constructor() {
    this.root = new TrieNode()
  }
  insert(key: string, val: number): void {
    // 1. 遍历 key 中的所有字符
    // 2. 如果字符原本并不在 Trie 中，则将字符保存在 Trie 中
    // 3. 遍历完 key 中的所有字符之后，在最有一个节点中赋值 value
    let cur = this.root
    for (const c of key) {
      if (!cur.next.get(c)) {
        cur.next.set(c, new TrieNode())
      }
      cur = cur.next.get(c) as TrieNode
    }
    cur.value = val
  }
  sum(prefix: string): number {
    // 1. 遍历 prefix 中的所有字符，如果 prefix 中的字符不在 Trie 中，那么直接返回0
    // 2. 如果 prefix 中的字符为单词的结尾，直接累加节点的 value 值
    // 3. 当遍历完字符之后，递归遍历其后的所有节点的 next
    let cur = this.root
    for (const c of prefix) {
      const tmp = cur.next.get(c)
      if (!tmp) {
        return 0
      }
      cur = tmp
    }
    const result = cur.value + this.recursion(cur)
    return result
  }
  private recursion(node: TrieNode) {
    // 1. 遍历节点 node 的所有 next 节点
    // 2. 如果 next 的某个节点有 value，则与 result 进行相加
    // 3. 对该节点进行递归
    let result = 0
    for (let key of node.next.keys()) {
      const nextNode = node.next.get(key) as TrieNode
      if (nextNode.value) {
        result += nextNode.value
      }
      result += this.recursion(nextNode)
    }
    return result
  }
}