https://leetcode.com/problems/map-sum-pairs/description/
Problem:
Implement a MapSum class with insert, and sum methods.
For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.
For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.
Example 1:
|
1 2 3 4 |
Input: insert("apple", 3), Output: Null Input: sum("ap"), Output: 3 Input: insert("app", 2), Output: Null Input: sum("ap"), Output: 5 |
Idea:
Prefix tree
Solution 1
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
// Author: Huahua // Running time: 3 ms class MapSum { public: /** Initialize your data structure here. */ MapSum() {} void insert(const string& key, int val) { int inc = val; if (vals_.count(key)) { inc -= vals_[key]; } vals_[key] = val; for (int i = 1; i <= key.length(); ++i) sums_[key.substr(0,i)] += inc; } int sum(const string& prefix) { return sums_[prefix]; } private: unordered_map<string, int> vals_; unordered_map<string, int> sums_; }; |
Solution 2:
|
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 |
class MapSum { public: /** Initialize your data structure here. */ MapSum() {} void insert(string key, int val) { int inc = val - vals_[key]; Trie* p = &root; for (const char c : key) { if (!p->children[c]) p->children[c] = new Trie(); p->children[c]->sum += inc; p = p->children[c]; } vals_[key] = val; } int sum(string prefix) { Trie* p = &root; for (const char c : prefix) { if (!p->children[c]) return 0; p = p->children[c]; } return p->sum; } private: struct Trie { Trie():children(128, nullptr), sum(0){} ~Trie() { for (auto child : children) if (child) delete child; children.clear(); } vector<Trie*> children; int sum; }; Trie root; // dummy root unordered_map<string, int> vals_; // key -> val }; |
with std::unique_ptr
|
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 |
// Author: Huahua // Running time: 5 ms class MapSum { public: /** Initialize your data structure here. */ MapSum(): root_(new Trie()) {} void insert(string key, int val) { int inc = val - vals_[key]; Trie* p = root_.get(); for (const char c : key) { if (!p->children[c]) p->children[c] = new Trie(); p->children[c]->sum += inc; p = p->children[c]; } vals_[key] = val; } int sum(string prefix) { Trie* p = root_.get(); for (const char c : prefix) { if (!p->children[c]) return 0; p = p->children[c]; } return p->sum; } private: struct Trie { Trie():children(128, nullptr), sum(0){} ~Trie() { for (auto child : children) if (child) { delete child; child = nullptr; } children.clear(); } vector<Trie*> children; int sum; }; std::unique_ptr<Trie> root_; unordered_map<string, int> vals_; // key -> val }; |