Algorithm

Problem Name: 677. Map Sum Pairs

Problem Link: https://leetcode.com/problems/map-sum-pairs/
 

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:

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.

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


class MapSum {
    struct TrieNode{
        int sum;
        TrieNode* next[26];
        TrieNode(): sum(0){
            memset(next, NULL, sizeof(next));
        }
    };
    
    unordered_map < string, int>m;
    TrieNode* root;
    
public:
    /** Initialize your data structure here. */
    MapSum() {
        root = new TrieNode();
    }
    
    void insert(string key, int val) {
        bool replace = false;
        if(m.count(key)) replace = true;
        TrieNode* p = root;
        for(char c: key){
            if(!p->next[c - 'a']) p->next[c - 'a'] = new TrieNode();
            p = p->next[c - 'a'];
            p->sum += replace ? val - m[key] : val;
        }
        m[key] = val;
    }
    
    int sum(string prefix) {
        TrieNode* p = root;
        for(char c: prefix){
            if(!p->next[c - 'a']) return 0;
            p = p->next[c - 'a'];
        }
        return p->sum;
    }
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

x
–
+
cmd
[null, null, 3, null, 5]

#2 Code Example with Java Programming

Code - Java Programming


class MapSum {

  /** Initialize your data structure here. */
  TrieNode root;
  Map < String, Integer> map;
  public MapSum() {
    root = new TrieNode('-');
    map = new HashMap < >();
  }

  public void insert(String key, int val) {
    int delta = val - map.getOrDefault(key, 0);
    map.put(key, val);
    TrieNode curr = root;
    for (int i = 0; i  <  key.length(); i++) {
      if (!curr.map.containsKey(key.charAt(i))) {
        curr.map.put(key.charAt(i), new TrieNode(key.charAt(i)));
      }
      curr = curr.map.get(key.charAt(i));
      curr.score += delta;
    }
  }

  public int sum(String prefix) {
    TrieNode curr = root;
    for (int i = 0; i  <  prefix.length(); i++) {
      if (!curr.map.containsKey(prefix.charAt(i))) {
        return 0;
      }
      curr = curr.map.get(prefix.charAt(i));
    }
    return curr.score;
  }
}

class TrieNode {
  char c;
  Map < Character, TrieNode> map;
  int score;
  
  public TrieNode(char c) {
    this.c = c;
    map = new HashMap < >();
    score = 0;
  }
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

x
–
+
cmd
[null, null, 3, null, 5]

#3 Code Example with Javascript Programming

Code - Javascript Programming


const MapSum = function() {
  this.hash = {};
};

MapSum.prototype.insert = function(key, val) {
  this.hash[key] = val;
};

MapSum.prototype.sum = function(prefix) {
  let res = 0;
  Object.keys(this.hash).forEach(el => {
    if (el.indexOf(prefix) === 0) {
      res += this.hash[el];
    }
  });
  return res;
};
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

x
–
+
cmd
[null, null, 3, null, 5]

#4 Code Example with Python Programming

Code - Python Programming


class MapSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        from collections import defaultdict
        self.dic = defaultdict(int)

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: void
        """
        self.dic[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        sm = 0
        for k in self.dic:
            if k[:len(prefix)] == prefix: sm += self.dic[k]
        return sm


# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["MapSum", "insert", "sum", "insert", "sum"] [[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]

Output

x
–
+
cmd
[null, null, 3, null, 5]
Advertisements

Demonstration

Previous
#676 Leetcode Implement Magic Dictionary Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#678 Leetcode Valid Parenthesis String Solution in C, C++, Java, JavaScript, Python, C# Leetcode