本文主要是介绍Map Sum Pairs问题及解法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题描述：
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.
示例:
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5
问题分析：
对于含有公共前缀的字符串问题，我们可以考虑利用Trie数据结构，将字符串存储起来，每次求和时，若给定的公共前缀不存在，直接返回0；若存在，可以递归遍历出所有含有公共前缀的字串对应值的和。
过程详见代码：
class Trie{
public:Trie * children[26];bool isLeaf;int val;
public:Trie(){for (int i = 0; i < 26; i++) children[i] = nullptr;isLeaf = false;val = 0;}
};class MapSum {
public:Trie * root;/** Initialize your data structure here. */MapSum() {root = new Trie();}void insert(string key, int val) {if (key == "") return;Trie * tRoot = root;for (int i = 0; i < key.length(); i++){if (tRoot->children[key[i] - 'a'] == nullptr){tRoot->children[key[i] - 'a'] = new Trie();}tRoot = tRoot->children[key[i] - 'a'];}tRoot->isLeaf = true;tRoot->val = val;}int sum(string prefix) {Trie * tRoot = root;int res = 0;for (int i = 0; i < prefix.length(); i++){if (tRoot->children[prefix[i] - 'a'] != nullptr) tRoot = tRoot->children[prefix[i] - 'a'];else return 0;}blsum(tRoot, res);return res;}void blsum(Trie * tRoot, int& res){if (tRoot == nullptr) return;if (tRoot->isLeaf) res += tRoot->val;for (int i = 0; i < 26; i++){blsum(tRoot->children[i], res);}}
};/*** Your MapSum object will be instantiated and called as such:* MapSum obj = new MapSum();* obj.insert(key,val);* int param_2 = obj.sum(prefix);*/这篇关于Map Sum Pairs问题及解法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
