> For the complete documentation index, see [llms.txt](https://protegejj.gitbook.io/algorithm-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://protegejj.gitbook.io/algorithm-practice/leetcode/trie/677-map-sum-pairs.md).

# 677 Map Sum Pairs

## 677.[Map Sum Pairs](https://leetcode.com/problems/map-sum-pairs/description/)

## 1. Question

Implement a MapSum class with`insert`, and`sum`methods.

For the method`insert`, you'll be given a pair of (string, integer). The string represents the key and the integer represents the value. **If the key already existed, then the original key-value pair will be overridden to the new one**.

For the method`sum`, you'll be given a string representing the prefix, and you need to return the sum of all the pairs' value whose key starts with the prefix.

**Example 1:**

```
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
```

## 2. Implementation

**(1) Trie**

```java
class MapSum {
    class TrieNode {
        char val;
        int sum;
        boolean isWord;
        TrieNode[] childNode;

        public TrieNode(char val, int sum) {
            this.val = val;
            this.sum = sum;
            childNode = new TrieNode[256];
        }
    }

    class Trie {
        TrieNode root;

        public Trie() {
            root = new TrieNode(' ', 0);
        }

        public void insert(String word, int val, boolean overridden) {
            TrieNode curNode = root;

            for (char c : word.toCharArray()) {
                if (curNode.childNode[c] == null) {
                    curNode.childNode[c] = new TrieNode(c, val);
                }
                else {
                    if (overridden) {
                       curNode.childNode[c].sum = val;
                    }
                    else {
                       curNode.childNode[c].sum += val; 
                    }
                }
                curNode = curNode.childNode[c];
            }
            curNode.isWord = true;
        }

        public int searchByPrefix(String word) {
            TrieNode curNode = root;

            if (word == null || word.length() == 0) {
                return 0;
            }

            for (char c : word.toCharArray()) {
                if (curNode.childNode[c] == null) {
                    return 0;
                }
                curNode = curNode.childNode[c];
            }
            return curNode.sum;
        }
    }

    Trie trie;
    Set<String> set;
    /** Initialize your data structure here. */
    public MapSum() {
        trie = new Trie();
        set = new HashSet<>();
    }

    public void insert(String key, int val) {
        trie.insert(key, val, set.contains(key));
        set.add(key);
    }

    public int sum(String prefix) {
        return trie.searchByPrefix(prefix);
    }
}

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

## 3. Time & Space Complexity

Trie: insert(): 时间复杂度O(L),L为insert的word的长度, sum(): 时间复杂度O(n)，n 为输入的prefix的长度，空间复杂度: O(m), m为插入insert的word的个数