# 677.键值映射

<https://leetcode-cn.com/problems/map-sum-pairs>

* [677.键值映射](#677键值映射)
  * [题目描述](#题目描述)
  * [方法 1：HashMap](#方法-1hashmap)
    * [复杂度分析](#复杂度分析)
    * [代码](#代码)
  * [方法 2：Trie + DFS](#方法-2trie--dfs)
    * [思路](#思路)
    * [复杂度分析](#复杂度分析-1)
    * [代码](#代码-1)
  * [方法 3：Trie + 时间优化](#方法-3trie--时间优化)
    * [思路](#思路-1)
    * [复杂度分析](#复杂度分析-2)
    * [代码](#代码-2)
  * [方法 4：Trie + HashMap](#方法-4trie--hashmap)
    * [思路](#思路-2)
    * [复杂度分析](#复杂度分析-3)
    * [代码](#代码-3)

## 题目描述

```
实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
输入: sum("ap"), 输出: 3
输入: insert("app", 2), 输出: Null
输入: sum("ap"), 输出: 5

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/map-sum-pairs
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
```

## 方法 1：HashMap

### 复杂度分析

|        | 时间                                  | 空间       |
| ------ | ----------------------------------- | -------- |
| insert | $O(1)$ (不考虑哈希冲突的话)                  | $O(n)$   |
| sum    | $O(n\*len(prefix))$                 | $O(n)$   |
| 备注     | n 是 hashmap 的 key 总数，prefix 是要查找的前缀 | n 是字符串数量 |

### 代码

Python Code

```python
class MapSum(object):
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.hashmap = {}

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: None
        """
        self.hashmap[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        res = 0
        for key in self.hashmap:
            if key.startswith(prefix):
                res += self.hashmap[key]
        return res



# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
```

## 方法 2：Trie + DFS

### 思路

* 构建前缀树。
* `sum` 操作的时候，先判断 `prefix` 是否存在前缀树中，然后找到 `prefix` 最后的节点，开始 DFS。

**DFS**

* **大问题**：`dfs(node)` 应该要返回以这个节点开始的所有路径中的 `value` 的和。
* **小问题**：`dfs(node.child)`，先找到以 `node` 的子节点开始的所有路径中的 `value` 的和。不过由于 `node` 有很多子节点，所以我们需要一个循环。
* **大问题与小问题的关系**：当我们求出了全部 `dfs(node.child)`，那么
  * `dfs(node) = node.value + dfs(node.child1) + dfs(node.child2) + ...`
* **递归出口**：如果节点不存在，我们直接返回 0，停止递归。

### 复杂度分析

* 时间复杂度：`insert` 操作的时间复杂度是 $O(len(key))$，`sum` 操作的时间复杂度是 $O(m^{n})$，m 是字符集中字符数量，n 是字符串长度。
* 空间复杂度：$O(m^{n})$，m 是字符集中字符数量，n 是字符串长度。

|        | 时间                   | 空间         |
| ------ | -------------------- | ---------- |
| insert | $O(len(key))$        | $O(m^{n})$ |
| sum    | $O(m^{n})$           | $O(m^{n})$ |
| 备注     | m 是字符集中字符数量，n 是字符串长度 |            |

### 代码

TypeScript Code

```typescript
class TrieNode {
    value: number;
    children: Array<TrieNode>;

    constructor(value: number) {
        this.value = value;
        this.children = Array(26);
    }
}

class MapSum {
    private root: TrieNode;

    constructor() {
        this.root = this._getTrieNode(0);
    }

    private _getTrieNode(value: number): TrieNode {
        return new TrieNode(value);
    }

    private _char2Index(char: string): number {
        return char.toLowerCase().charCodeAt(0) - 97;
    }

    insert(key: string, val: number): void {
        let crawl: TrieNode = this.root;
        for (let char of key) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) {
                crawl.children[index] = this._getTrieNode(0);
            }
            crawl = crawl.children[index];
        }
        crawl.value = val;
    }

    private _dfs(crawl: TrieNode): number {
        if (!crawl) return 0;

        return crawl.children.reduce(
            (res: number, pointer: TrieNode): number => {
                return res + (pointer ? this._dfs(pointer) : 0);
            },
            crawl.value,
        );
    }

    sum(prefix: string): number {
        let crawl: TrieNode = this.root;
        for (let char of prefix) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) return 0;
            crawl = crawl.children[index];
        }
        return this._dfs(crawl);
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */
```

## 方法 3：Trie + 时间优化

### 思路

在每个节点上存 `prefixSum`，可以把 `sum` 操作的时间复杂度降到 $O(1)$，代价是在 `insert` 的时候需要先检查 key 是否已经存在，存在的话要先从 `prefixSum` 中减去旧的 value，再加上新的 value。

### 复杂度分析

|        | 时间            | 空间                   |
| ------ | ------------- | -------------------- |
| insert | $O(len(key))$ | $O(m^{n})$           |
| sum    | $O(1)$        | $O(m^{n})$           |
| 备注     |               | m 是字符集中字符数量，n 是字符串长度 |

### 代码

```typescript
class TrieNode {
    value: number;
    prefixSum: number;
    children: Array<TrieNode>;

    constructor(value: number) {
        this.value = value;
        this.prefixSum = 0;
        this.children = Array(26);
    }
}

class MapSum {
    private root: TrieNode;

    constructor() {
        this.root = this._getTrieNode(0);
    }

    private _getTrieNode(value: number): TrieNode {
        return new TrieNode(value);
    }

    private _char2Index(char: string): number {
        return char.toLowerCase().charCodeAt(0) - 97;
    }

    search(key: string): number {
        let crawl: TrieNode = this.root;
        for (let char of key) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) return 0;
            crawl = crawl.children[index];
        }
        return crawl.value;
    }

    insert(key: string, val: number): void {
        let crawl: TrieNode = this.root;
        const existedVal: number = this.search(key);
        for (let char of key) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) {
                crawl.children[index] = this._getTrieNode(0);
            }
            crawl = crawl.children[index];
            crawl.prefixSum = crawl.prefixSum - existedVal + val;
        }
        crawl.value = val;
    }

    sum(prefix: string): number {
        let crawl: TrieNode = this.root;

        for (let char of prefix) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) return 0;
            crawl = crawl.children[index];
        }
        return crawl.prefixSum;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */
```

## 方法 4：Trie + HashMap

### 思路

在方法 3 的基础上再加一个 hashmap，把以某个前缀开始的 `key` 和相应的 `value`存起来，比如，

* 我们先插入了一个 `(dark, 3)`，然后再插入一个 `(darkest, 2)`
* 这时的 hashmap 应该是这样：
  * `{ dark: 3, darkest: 2 }`
* 这时如果我们再次插入 `(darkest, 5)`，覆盖了之前的值，那 hashmap 就变成了：
  * `{ dark: 3, darkest: 5 }`

### 复杂度分析

|        | 时间               | 空间                   |
| ------ | ---------------- | -------------------- |
| insert | $O(len(key))$    | $O(m^{n})$           |
| sum    | $O(len(prefix))$ | $O(m^{n})$           |
| 备注     |                  | m 是字符集中字符数量，n 是字符串长度 |

### 代码

```typescript
class TrieNode {
    value: number;
    prefixSum: number;
    children: Array<TrieNode>;

    constructor(value: number) {
        this.value = value;
        this.prefixSum = 0;
        this.children = Array(26);
    }
}

class MapSum {
    private root: TrieNode;
    private existedWords: {
        [key: string]: number;
    };

    constructor() {
        this.root = this._getTrieNode(0);
        this.existedWords = {};
    }

    private _getTrieNode(value: number): TrieNode {
        return new TrieNode(value);
    }

    private _char2Index(char: string): number {
        return char.toLowerCase().charCodeAt(0) - 97;
    }

    insert(key: string, val: number): void {
        let crawl: TrieNode = this.root;
        for (let char of key) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) {
                crawl.children[index] = this._getTrieNode(0);
            }
            crawl = crawl.children[index];
            if (key in this.existedWords) {
                crawl.prefixSum -= this.existedWords[key];
            }
            crawl.prefixSum += val;
        }
        this.existedWords[key] = val;
        crawl.value = val;
    }

    sum(prefix: string): number {
        let crawl: TrieNode = this.root;

        for (let char of prefix) {
            const index: number = this._char2Index(char);
            if (!crawl.children[index]) return 0;
            crawl = crawl.children[index];
        }
        return crawl.prefixSum;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * var obj = new MapSum()
 * obj.insert(key,val)
 * var param_2 = obj.sum(prefix)
 */
```

更多题解可以访问：<https://github.com/suukii/91-days-algorithm>