677. Key-value mapping

This is my first post in a series that will continue in a long time, with C++ as the main language for solving the questions, perhaps JavaScript, Go, Rust.

I pursue simple and easy to read programming style, and I will use STL library or new features (C++11, 17) as little as possible. Please reply if you have any questions.

Title link: 677. Key value Mapping – Force Buckle (LeetCode) (leetcode-cn.com)

Difficulty: Medium

Build a Trie tree with one character per node, updating the value at the end of the inserted word. When searching, find the node where the final character is located, and recursively find the sum of subtrees.

class Trie {
    private:
        Trie *nex[26];
        int val;
    public:
        Trie(){
            val = 0;
            memset(nex,0.sizeof(nex));
        }
        void insert(string key, int val){
            Trie* tr = this;
            for(char ch:key){
                if(! tr->nex[ch-'a']){
                    tr->nex[ch-'a'] = new Trie(a); } tr = tr->nex[ch-'a'];
            }
            tr->val = val;
        }
        int sum(string prefix){
            Trie* tr = this;
            for(char ch:prefix){
                // There is no path prefixed with this word, denoted as 0
                if(! tr->nex[ch-'a']) {return 0;
                }
                tr = tr->nex[ch-'a'];
            }
            return sub(tr);
        }
        int sub(Trie* tr){
            int sum = tr->val;
            for(int i=0; i<26; i++){if(tr->nex[i]){
                    sum += sub(tr->nex[i]); }}returnsum; }};class MapSum {
private:
    Trie* tr;
public:
    MapSum() {
        tr = new Trie(a); }void insert(string key, int val) {
        tr->insert(key,val);
    }
    
    int sum(string prefix) {
        return tr->sum(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); * /
Copy the code