# LeetCode- Map Sum Pairs Solution

### 题目：

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```

### 实现：

• 蛮力解法：已字符串为key和计数为value创建HashMap，进行sum 时遍历HashMap，如果该键以给定的前缀开头，则进行累计。   时间复杂度 O(N), 空间复杂度O(N)
``````
class MapSum {

private HashMap<String, Integer> map;
/** Initialize your data structure here. */
public MapSum() {
map = new HashMap<>();
}

public void insert(String key, int val) {
map.put(key, val);
}

public int sum(String prefix) {
int ans = 0;
for (String key: map.keySet()){
if (key.startsWith(prefix)){
ans += map.get(key);
}
}

return ans;
}
}
``````
•  前缀hash：单独创建一个SumMap存放前缀所有出现的累计值，当插入键值对时Map，SumMap记录所有前缀子串的值val， 如果插入键值对已存在。 SumMap记录其变化值  val – map.getOrDefault(key, 0)。  时间复杂度 O(N), 空间复杂度O(N)
``````class MapSum {

private Map <String, Integer> map;
private Map <String, Integer> summap;

public MapSum() {
map = new HashMap<>();
summap = new HashMap<>();
}

public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
String prefix = "";
for (char c: key.toCharArray()){
prefix += c;
summap.put(prefix, summap.getOrDefault(prefix, 0)+delta);
}
}

public int sum(String prefix) {

return summap.getOrDefault(prefix, 0);
}
}``````
• Trie： Tire节点中增加一个计数器即可, 流程与上一个解法一致。

``````class TrieNode {
Map<Character, TrieNode> children = new HashMap();
Integer score = new Integer(0);
}

class MapSum {

private  TrieNode root;
private  Map<String, Integer> map;

public MapSum() {
root = new TrieNode();
map = new HashMap();
}

public void insert(String key, int val) {
int delta = val - map.getOrDefault(key, 0);
map.put(key, val);
TrieNode cur = root;
cur.score += delta;
for (char c: key.toCharArray()){
cur.children.putIfAbsent(c, new TrieNode());
cur = cur.children.get(c);
cur.score += delta;
}
}

public int sum(String prefix) {

TrieNode cur = root;
for (char c: prefix.toCharArray()){
cur = cur.children.get(c);
if (cur == null ){
return 0;
}
}
return cur.score;
}

}``````

### 参考及引用：

https://leetcode.com/problems/map-sum-pairs/solution/

Photo by Steve Johnson from Pexels