# [LeetCode 677. Map Sum Pairs ](https://leetcode.com/explore/challenge/card/july-leetcoding-challenge-2021/612/week-5-july-29th-july-31st/3832/)
### Daily challenge Jul 30, 2021 (MEDIAN)

>Implement the `MapSum` class:
>
>* **`MapSum()`** Initializes the `MapSum` object.
>* **`void insert(String key, int val)`** Inserts the `key-val` pair into the map. If the `key` already existed, the original `key-value` pair will be overridden to the new one.
>* **`int sum(string prefix)`** Returns the sum of all the pairs' value whose `key` starts with the `prefix`.

:::info
**Example 1:**
**Input**
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
**Output**
[null, null, 3, null, 5]

**Explanation**
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)
:::

:::warning
**Constraints:**
* 1 <= key.length, prefix.length <= 50
* key and prefix consist of only lowercase English letters.
* 1 <= val <= 1000
* At most 50 calls will be made to insert and sum.
:::

---

### Approach 1 : Hash Map :bulb:
**`4 ms ( 68.72% )`**
**`Insert ---> O(1)`**
**`Sum ---> O(K * P)`** `K、P are length of key & prefix`

* **insert** : `map` 只記錄輸入的 `key、val`。
* **sum** : 從 `map` 中遍歷每個 `map.first`，判斷他的開頭是否與 `prefix` 相同。

class MapSum {
public:
    /** Initialize your data structure here. */
    MapSum() {  
    }
    
    void insert(string key, int val) {
        list[key] = val;
    }
    
    bool check(string key, string prefix){
        int size_pre = prefix.length();
        int size_key = key.length();
        
        if(size_key < size_pre) return false;
        
        for(int i=0; i<size_pre; i++){
            if(key[i] != prefix[i]) return false;
        }
        
        return true;
    }
    
    int sum(string prefix) {
        int ans = 0;

        for(auto LIST : list){
            string key = LIST.first;
            if(check(key, prefix))  ans += LIST.second;
        }
        
        return ans;
    }
    
private:
    unordered_map<string, int> list;
};

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

---

### Approach 2 : Trie :book:
**`0 ms ( 100% )`**
**`Insert ---> O(K)`**
**`Sum ---> O(P)`**

:::success
:::

* 一開始先宣告一個 `TrieNode root`。
* **insert** :
> 1. `dif` 表示與原本字串 `val` 的差值 ---> **`dif = val - used[key]`**。
> ( 因為規定 `insert` 相同字串時，原本的 `val` 會被覆蓋掉 )
> 2. 遍歷 `key` 內所有的元素，
>>* `建立新的 TrieNode` ( 若指到 `node` 為空 )
>>---> **`current->node[c] = new TrieNode()`**。
>>* `更改 val` ---> **`current = current->node[c]()`**。
>>* `更新 current` ---> **`current = current->node[c]`**。
> 3. 最後將 `key` 記錄到 `map`。

* sum :
> 根據 `prefix` 的字元向下搜尋 `node`
>> * 若 **`current->node[c] == NULL`**，表示沒有該字串 ---> 回傳 **`0`**。
>> * 若能找到 ---> 回傳 **`current->sum`**。

struct TrieNode{
    TrieNode* node[26] = {};
    int sum = 0;
};

class MapSum {
public:
    unordered_map<string, int> used;
    TrieNode root;
    
    MapSum() {  
    }
    
    void insert(string key, int val) {
        TrieNode* current = &root;
        int dif = val - used[key];
        
        for(char c : key){
            c -= 'a';
            
            if(current->node[c] == NULL)   current->node[c] = new TrieNode();
            current = current->node[c];
            current->sum += dif;
        }
        used[key] = val;
    }
     
    int sum(string prefix) {
        TrieNode* current = &root;
        
        for(char c : prefix){
            c -= 'a';
            if(current->node[c] == NULL)    return 0;
            current = current->node[c];
        }
        
        return current->sum;
    }
};

---

### Approach 3 : Trie + Hash Map :book:
**`0 ms ( 100% )`**
**`Insert ---> O(K^2)`**
**`Sum ---> O(1)`**

* **insert** : 與 `Approach 2` 相似。
> 1. **`dif = val - used[key]`** 表示與原本字串 `val` 的差值。
> 2. 將 `key` 存入 `used` ---> **`used[key] = val;`**。
> 3. 遍歷 `key`，將所有可能的 `prefix` 存入 `SUM` ---> **`SUM[prefix] += dif`**。

* **sum** : 直接回傳 `SUM[prefix]`

class MapSum {
public:
    unordered_map<string, int> used;
    unordered_map<string, int> SUM;
    
    MapSum() {  
    }
    
    void insert(string key, int val) {
        int dif = val - used[key];
        used[key] = val;
        
        string prefix;
        for(char c : key){
            prefix += c;
            SUM[prefix] += dif;
        }
    }
     
    int sum(string prefix) {
        return  SUM[prefix];
    }
};