Date：2019-4-21

题目地址：https://leetcode-cn.com/problems/map-sum-pairs/

实现一个 MapSum 类里的两个方法，insert 和 sum。
对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。
对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:
输入:

insert(“apple”, 3), 输出: Null

输入:

sum(“ap”), 输出: 3

输入:

insert(“app”, 2), 输出: Null

输入:

sum(“ap”), 输出: 5

解题：

1. 使用 Map 函数：

  1. /**
  2.  * Initialize your data structure here.
  3.  */
  4. const MapSum = function() {
  5.   this.dic = new Map()
  6. }
  8. /** 
  9.  * @param {string} key 
  10.  * @param {number} val
  11.  * @return {void}
  12.  */
  13. MapSum.prototype.insert = function(key, val) {
  14.   this.dic.set(key,val)
  15. }
  17. /** 
  18.  * @param {string} prefix
  19.  * @return {number}
  20.  */
  21. MapSum.prototype.sum = function(prefix) {
  22.   let result = 0
  23.   this.dic.forEach((val,key) => {
  24.     if(key.indexOf(prefix) === 0){
  25.       result += val
  26.     }
  27.   })
  28.   return result
  29. }
  31. /** 
  32.  * Your MapSum object will be instantiated and called as such:
  33.  * var obj = new MapSum()
  34.  * obj.insert(key,val)
  35.  * var param_2 = obj.sum(prefix)
  36.  */

2. 前缀Trie：

  1. /**
  2.  * Initialize your data structure here.
  3.  */
  4. const TrieN = function(key){
  5.   this.key = key
  6.   this.val = 0
  7.   this.child = new Map()
  8. }
  10. TrieN.prototype.insert = function(key, val) {
  11.   if(!key) {
  12.     this.val = val
  13.     return
  14.   }
  16.   // 单字母插入
  17.   let n = this.child.get(key[0])
  18.   if (!n) {
  19.     n = new TrieN(key[0])
  20.     this.child.set(key[0], n)
  21.   }
  23.   n.insert(key.substr(1), val)
  24. }
  26. TrieN.prototype.sum = function(prefix) {
  27.   if(!prefix) {
  28.     return this.calculate()
  29.   }
  31.   let n = this.child.get(prefix[0])
  32.   if (!n) {
  33.       return 0    
  34.   }
  36.   return n.sum(prefix.substr(1))
  37. }
  39. TrieN.prototype.calculate = function(){
  40.   let ret = this.val
  41.   for(let value of this.child.values()){
  42.     ret += value.calculate()
  43.   }
  44.   return ret
  45. }
  47. /*
  48.  *    MapSum
  49.  */
  52. const MapSum = function() {
  53.   this.root = new TrieN("")
  54. }
  56. /** 
  57.  * @param {string} key 
  58.  * @param {number} val
  59.  * @return {void}
  60.  */
  61. MapSum.prototype.insert = function(key, val) {
  62.   if(!key) {
  63.     return
  64.   }
  65.   this.root.insert(key, val)
  66. }
  68. /** 
  69.  * @param {string} prefix
  70.  * @return {number}
  71.  */
  72. MapSum.prototype.sum = function(prefix) {
  73.   if(!prefix){
  74.     return 0
  75.   }
  76.   return this.root.sum(prefix)
  77. }
  79. /** 
  80.  * Your MapSum object will be instantiated and called as such:
  81.  * var obj = new MapSum()
  82.  * obj.insert(key,val)
  83.  * var param_2 = obj.sum(prefix)
  84.  */

为什么要做这道题，它的实际运用场景是什么

js中对于前缀Trie的应用和Map函数的使用