C++刷leetcode（677. 键值映射）【字典树】

糖逗

题目描述:

实现一个 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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class MapSum {
private:
    bool isEnd;
    MapSum* next[26];
    vector<int> value;
    set<string> store;
public:
    /** Initialize your data structure here. */
    MapSum() {
        isEnd = false;
        memset(next, 0, sizeof(next));
        value = {};
    }
    
    void insert(string key, int val) {
        MapSum* node = this;
        auto cha = store.insert(key);
        bool flag = cha.second;
        for(auto cha : key){
            if(node -> next[cha - 'a'] == NULL){
                node -> next[cha - 'a'] = new MapSum();
            }
            node = node -> next[cha - 'a'];
            if(flag == false)node -> value.pop_back(); 
            node ->value.push_back(val);
        }
        node -> isEnd = true;
    }
    
    int sum(string prefix) {
        MapSum*node = this;
        int res = 0;
        for(auto cha : prefix){
            if(node -> next[cha - 'a'] == NULL) return res;
            node = node -> next[cha - 'a'];
        }
        int len = node -> value.size();
        for(int i = 0; i < len; i++){
            res += node -> value[i];
        }
        return res;
    }
};

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