Map Sum Pairs Solutions in C++

/// Source : https://leetcode.com/problems/map-sum-pairs/description/
/// Author : liuyubobobo
/// Time   : 2017-11-05

#include <iostream>
#include <unordered_map>

using namespace std;

/// HashMap + Brute Force
/// Time Complexity: insert: O(1)
///                  sum: O(n * len(prefix))
/// Space Complexity: O(sum(len(wi))) where wi is the length of the ith word.
class MapSum {

private:
    unordered_map<string, int> mapsum;

public:
    /** Initialize your data structure here. */
    MapSum() {
        mapsum.clear();
    }

    void insert(string key, int val) {
        mapsum[key] = val;
    }

    int sum(string prefix) {
        int ret = 0;
        for(pair<string, int> e: mapsum)
            if(e.first.substr(0, prefix.size()) == prefix)
                ret += e.second;
        return ret;
    }
};

int main() {

    MapSum obj;
    obj.insert("apple", 3);
    cout << obj.sum("ap") << endl; // 3
    obj.insert("app", 2);
    cout << obj.sum("ap") << endl; // 5

    return 0;
}

/// Source : https://leetcode.com/problems/map-sum-pairs/description/
/// Author : liuyubobobo
/// Time   : 2017-11-05

#include <iostream>
#include <unordered_map>

using namespace std;

/// Prefix HashMap + Brute Force
/// Time Complexity: insert: O(len(prefix)^2)
///                  sum: O(len(prefix))
/// Space Complexity: O(sum(len(wi)^2)) where wi is the length of the ith word.
class MapSum {

private:
    unordered_map<string, int> prefixScore;
    unordered_map<string, int> summap;
public:
    /** Initialize your data structure here. */
    MapSum() {
        summap.clear();
        prefixScore.clear();
    }

    void insert(string key, int val) {

        if(summap.find(key) == summap.end()){
            for(int i = 1 ; i <= key.size() ; i ++)
                prefixScore[key.substr(0, i)] += val;
        }
        else{
            for(int i = 1 ; i <= key.size() ; i ++)
                prefixScore[key.substr(0, i)] = val;
        }

        summap[key] = val;
    }

    int sum(string prefix) {
        return prefixScore[prefix];
    }
};

int main() {

    MapSum obj;
    obj.insert("apple", 3);
    cout << obj.sum("ap") << endl; // 3
    obj.insert("app", 2);
    cout << obj.sum("ap") << endl; // 5

    return 0;
}

/// Source : https://leetcode.com/problems/map-sum-pairs/description/
/// Author : liuyubobobo
/// Time   : 2017-11-05

#include <iostream>
#include <map>
#include <vector>

using namespace std;

/// Trie
/// Time Complexity: insert: O(len(prefix))
///                  sum: O(sum(len(wi)))
/// Space Complexity: O(sum(len(wi))) where wi is the length of the ith word.

class Trie{

private:
    struct Node{
        map<char, int> next;
        int val = 0;
    };
    vector<Node> trie;

public:
    Trie(){
        trie.clear();
        trie.push_back(Node());
    }

    void insert(const string& word, int val){
        insert(0, word, 0, val);
    }

    int sum(const string& prefix){
        int treeID = findTreeID(0, prefix, 0);
        if(treeID == -1)
            return 0;
        return dfs(treeID);
    }

private:
    void insert(int treeID, const string& word, int index, int val){

        if(index == word.size()) {
            trie[treeID].val = val;
            return;
        }

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end()){
            trie[treeID].next[word[index]] = trie.size();
            trie.push_back(Node());
        }

        insert(trie[treeID].next[word[index]], word, index + 1, val);
    }

    int findTreeID(int treeID, const string& word, int index){

        if(index == word.size())
            return treeID;

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end())
            return -1;

        return findTreeID(trie[treeID].next[word[index]], word, index + 1);
    }

    int dfs(int treeID){

        int res = trie[treeID].val;
        for(pair<char, int> next: trie[treeID].next)
            res += dfs(next.second);
        return res;
    }
};

class MapSum {

private:
    Trie trie;

public:

    void insert(string key, int val) {
        trie.insert(key, val);
    }

    int sum(string prefix) {
        return trie.sum(prefix);
    }
};

int main() {

    MapSum obj;
    obj.insert("apple", 3);
    cout << obj.sum("ap") << endl; // 3
    obj.insert("app", 2);
    cout << obj.sum("ap") << endl; // 5

    return 0;
}

/// Source : https://leetcode.com/problems/map-sum-pairs/description/
/// Author : liuyubobobo
/// Time   : 2017-11-05

#include <iostream>
#include <map>
#include <vector>

using namespace std;

/// Trie
/// Update key value when key already in the trie
/// Time Complexity: insert: O(len(prefix))
///                  sum: O(len(prefix))
/// Space Complexity: O(sum(len(wi))) where wi is the length of the ith word.

class Trie{

private:
    struct Node{
        map<char, int> next;
        int val = 0;
        bool end = false;
    };
    vector<Node> trie;

public:
    Trie(){
        trie.clear();
        trie.push_back(Node());
    }

    void insert(const string& word, int val){
        insert(0, word, 0, val);
//        cout << "After insert " << word << ", trie is:" << endl;
//        print();
    }

    int sum(const string& prefix){
        int treeID = findTreeID(0, prefix, 0);
        if(treeID == -1)
            return 0;
        return trie[treeID].val;
    }

private:
    int insert(int treeID, const string& word, int index, int val){

        if(index == word.size()) {

            if(trie[treeID].end){
                int change = val - trie[treeID].val;
                trie[treeID].val = val;
                return change;
            }
            else{
                trie[treeID].end = true;
                trie[treeID].val += val;
                return val;
            }
        }

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end()){
            trie[treeID].next[word[index]] = trie.size();
            trie.push_back(Node());
        }

        int change = insert(trie[treeID].next[word[index]], word, index + 1, val);
        trie[treeID].val += change;

        return change;
    }

    int findTreeID(int treeID, const string& word, int index){

        if(index == word.size())
            return treeID;

        if(trie[treeID].next.find(word[index]) == trie[treeID].next.end())
            return -1;

        return findTreeID(trie[treeID].next[word[index]], word, index + 1);
    }

    void print(){
        for(Node node: trie)
            cout << node.val << " ";
        cout << endl;
    }
};

class MapSum {

private:
    Trie trie;

public:

    void insert(string key, int val) {
        trie.insert(key, val);
    }

    int sum(string prefix) {
        return trie.sum(prefix);
    }
};

int main() {

    MapSum obj;
    obj.insert("apple", 3);
    cout << obj.sum("ap") << endl; // 3
    obj.insert("app", 2);
    cout << obj.sum("ap") << endl; // 5

    return 0;
}