Skip to content

677. 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.

Solution:

class MapSum {
    static Map<String, Integer> map;

    Trie trie;
    public MapSum() {
      map = new HashMap<>();
      trie = new Trie();
    }

    class Trie{
        static class TrieNode{
            Map<Character, TrieNode> children = new HashMap<>();
            int score = 0;
        }

        private TrieNode root;
        public Trie(){
            root = new TrieNode();
        }

        public void insert(String key, int val) {
            TrieNode cur = root;
            int delta = val - map.getOrDefault(key, 0);
            map.put(key, val);
            cur.score = cur.score + delta;
            for (char c : key.toCharArray()){
                cur.children.putIfAbsent(c, new TrieNode());
                cur = cur.children.get(c);
                cur.score += delta;
            }
        }

        public int sum(String prefix) {
            TrieNode cur = root;
            for (char c : prefix.toCharArray()){
                cur = cur.children.get(c);
                if (cur == null){
                    return 0;
                }
            }

            return cur.score;
        }

    }

    public void insert(String key, int val) {
        trie.insert(key, val);
    }

    public int sum(String prefix) {
        return trie.sum(prefix);
    }
}

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

class MapSum {
    static Map<String, Integer> map;
    static class TrieNode{
        Map<Character, TrieNode> children = new HashMap<>();
        int score;
    }
    private TrieNode root;
    public MapSum() {
      map = new HashMap<>();
      root = new TrieNode();

    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode cur = root;
        cur.score = cur.score + delta;
        for (char c : key.toCharArray()){
            cur.children.putIfAbsent(c, new TrieNode());
            cur = cur.children.get(c);
            cur.score += delta;
        }
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for (char c : prefix.toCharArray()){
            cur = cur.children.get(c);
            if (cur == null){
                return 0;
            }
        }

        return cur.score;
    }
}

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