[C++]LeetCode677. 键值映射

[C++]LeetCode677. 键值映射

677. 键值映射

题目：实现一个 MapSum 类，支持两个方法，insert 和 sum：

MapSum() 初始化 MapSum 对象
void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

示例：
输入：
[“MapSum”, “insert”, “sum”, “insert”, “sum”]
[[], [“apple”, 3], [“ap”], [“app”, 2], [“ap”]]
输出：
[null, null, 3, null, 5]

解释：
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)

class MapSum {
private:
    bool isEnd;//是否为最后一个字母
    MapSum * next[26];//构建字母映射表
    int value;//若为最后一个字母，存入其对应的键值
    //深度优先搜索
    int dfs(MapSum* root)
    {
        if(!root) return 0;
        int res = 0;
        //累加的条件：根节点不为空且isEnd为true
        if(root->isEnd) res += root->value;
        //接着遍历next数组中的以prefix开头的其他字符
        for(auto cur: root->next)
        {
            //递归累加结果
            res += dfs(cur);
        }
        return res;
    }
public:
    
    MapSum() {
        isEnd = false;
        memset(next, 0, sizeof(next));
        value = 0;
    }
    
    void insert(string key, int val) {
        MapSum * node = this;
        for(auto c : key)
        {
            if(node->next[c-'a'] == NULL)
                node->next[c-'a'] = new MapSum();
            node = node->next[c-'a'];
        }
        node->isEnd = true;
        node->value = val;
        
    }
    
    int sum(string prefix) {
        MapSum * node = this;
        //先寻找前缀prefix
        for(auto c : prefix)
        {
            if(node->next[c-'a'] == NULL) return 0;
            node = node->next[c-'a'];
        }
        //递归累加以prefix为前缀的其他字母的值value
        return dfs(node);
    }
};

[[C++]Leetcode超高效刷题顺序及题目详解笔记（持续更新中）]