677. Map Sum Pairs

Posted on Edited on In

677. Map Sum Pairs

Description

Difficulty: Medium

Related Topics: Hash Table, String, Design, Trie

Design a map that allows you to do the following:

  • Maps a string key to a given value.
  • Returns the sum of the values that have a key with a prefix equal to a given string.

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.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
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)

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.

Hints/Notes

  • Trie

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class MapSum {
public:
    struct TrieNode {
        int value;
        vector<TrieNode*> children;
        TrieNode() {
            value = 0;
            children = vector<TrieNode*>(26, nullptr);
        }
    };

    TrieNode* root;

    MapSum() {
        root = new TrieNode();
    }

    void insert(string key, int val) {
        TrieNode* head = root;
        for (char c : key) {
            if (head->children[c - 'a'] == nullptr) {
                head->children[c - 'a'] = new TrieNode();
            }
            head = head->children[c - 'a'];
        }
        head->value = val;
    }

    int sum(string prefix) {
        TrieNode* head = root;
        for (char c : prefix) {
            if (head->children[c - 'a'] == nullptr) {
                return 0;
            }
            head = head->children[c - 'a'];
        }
        return traverse(head);
    }

    int traverse(TrieNode* head) {
        if (head == nullptr) {
            return 0;
        }
        int sum = 0;
        for (TrieNode* child : head->children) {
            sum += traverse(child);
        }
        return sum + head->value;
    }
};

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