Welcome to Subscribe On Youtube

677. Map Sum Pairs

Description

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.

Solutions

  • class Trie {
        private Trie[] children = new Trie[26];
        private int val;
    
        public void insert(String w, int x) {
            Trie node = this;
            for (int i = 0; i < w.length(); ++i) {
                int idx = w.charAt(i) - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
                node.val += x;
            }
        }
    
        public int search(String w) {
            Trie node = this;
            for (int i = 0; i < w.length(); ++i) {
                int idx = w.charAt(i) - 'a';
                if (node.children[idx] == null) {
                    return 0;
                }
                node = node.children[idx];
            }
            return node.val;
        }
    }
    
    class MapSum {
        private Map<String, Integer> d = new HashMap<>();
        private Trie trie = new Trie();
    
        public MapSum() {
        }
    
        public void insert(String key, int val) {
            int x = val - d.getOrDefault(key, 0);
            d.put(key, val);
            trie.insert(key, x);
        }
    
        public int sum(String prefix) {
            return trie.search(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 Trie {
    public:
        Trie()
            : children(26, nullptr) {
        }
    
        void insert(string& w, int x) {
            Trie* node = this;
            for (char c : w) {
                c -= 'a';
                if (!node->children[c]) {
                    node->children[c] = new Trie();
                }
                node = node->children[c];
                node->val += x;
            }
        }
    
        int search(string& w) {
            Trie* node = this;
            for (char c : w) {
                c -= 'a';
                if (!node->children[c]) {
                    return 0;
                }
                node = node->children[c];
            }
            return node->val;
        }
    
    private:
        vector<Trie*> children;
        int val = 0;
    };
    
    class MapSum {
    public:
        MapSum() {
        }
    
        void insert(string key, int val) {
            int x = val - d[key];
            d[key] = val;
            trie->insert(key, x);
        }
    
        int sum(string prefix) {
            return trie->search(prefix);
        }
    
    private:
        unordered_map<string, int> d;
        Trie* trie = new Trie();
    };
    
    /**
     * 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 Trie:
        def __init__(self):
            self.children: List[Trie | None] = [None] * 26
            self.val: int = 0
    
        def insert(self, w: str, x: int):
            node = self
            for c in w:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    node.children[idx] = Trie()
                node = node.children[idx]
                node.val += x
    
        def search(self, w: str) -> int:
            node = self
            for c in w:
                idx = ord(c) - ord('a')
                if node.children[idx] is None:
                    return 0
                node = node.children[idx]
            return node.val
    
    
    class MapSum:
        def __init__(self):
            self.d = defaultdict(int)
            self.tree = Trie()
    
        def insert(self, key: str, val: int) -> None:
            x = val - self.d[key]
            self.d[key] = val
            self.tree.insert(key, x)
    
        def sum(self, prefix: str) -> int:
            return self.tree.search(prefix)
    
    
    # Your MapSum object will be instantiated and called as such:
    # obj = MapSum()
    # obj.insert(key,val)
    # param_2 = obj.sum(prefix)
    
    
  • type trie struct {
    	children [26]*trie
    	val      int
    }
    
    func (t *trie) insert(w string, x int) {
    	for _, c := range w {
    		c -= 'a'
    		if t.children[c] == nil {
    			t.children[c] = &trie{}
    		}
    		t = t.children[c]
    		t.val += x
    	}
    }
    
    func (t *trie) search(w string) int {
    	for _, c := range w {
    		c -= 'a'
    		if t.children[c] == nil {
    			return 0
    		}
    		t = t.children[c]
    	}
    	return t.val
    }
    
    type MapSum struct {
    	d map[string]int
    	t *trie
    }
    
    func Constructor() MapSum {
    	return MapSum{make(map[string]int), &trie{} }
    }
    
    func (this *MapSum) Insert(key string, val int) {
    	x := val - this.d[key]
    	this.d[key] = val
    	this.t.insert(key, x)
    }
    
    func (this *MapSum) Sum(prefix string) int {
    	return this.t.search(prefix)
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * obj := Constructor();
     * obj.Insert(key,val);
     * param_2 := obj.Sum(prefix);
     */
    
  • class Trie {
        children: Trie[];
        val: number;
    
        constructor() {
            this.children = new Array(26);
            this.val = 0;
        }
    
        insert(w: string, x: number) {
            let node: Trie = this;
            for (const c of w) {
                const i = c.charCodeAt(0) - 97;
                if (!node.children[i]) {
                    node.children[i] = new Trie();
                }
                node = node.children[i];
                node.val += x;
            }
        }
    
        search(w: string): number {
            let node: Trie = this;
            for (const c of w) {
                const i = c.charCodeAt(0) - 97;
                if (!node.children[i]) {
                    return 0;
                }
                node = node.children[i];
            }
            return node.val;
        }
    }
    
    class MapSum {
        d: Map<string, number>;
        t: Trie;
        constructor() {
            this.d = new Map();
            this.t = new Trie();
        }
    
        insert(key: string, val: number): void {
            const x = val - (this.d.get(key) ?? 0);
            this.d.set(key, val);
            this.t.insert(key, x);
        }
    
        sum(prefix: string): number {
            return this.t.search(prefix);
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * var obj = new MapSum()
     * obj.insert(key,val)
     * var param_2 = obj.sum(prefix)
     */
    
    
  • class Trie {
        constructor() {
            this.children = new Array(26);
            this.val = 0;
        }
    
        insert(w, x) {
            let node = this;
            for (const c of w) {
                const i = c.charCodeAt(0) - 97;
                if (!node.children[i]) {
                    node.children[i] = new Trie();
                }
                node = node.children[i];
                node.val += x;
            }
        }
    
        search(w) {
            let node = this;
            for (const c of w) {
                const i = c.charCodeAt(0) - 97;
                if (!node.children[i]) {
                    return 0;
                }
                node = node.children[i];
            }
            return node.val;
        }
    }
    
    var MapSum = function () {
        this.d = new Map();
        this.t = new Trie();
    };
    
    /**
     * @param {string} key
     * @param {number} val
     * @return {void}
     */
    MapSum.prototype.insert = function (key, val) {
        const x = val - (this.d.get(key) ?? 0);
        this.d.set(key, val);
        this.t.insert(key, x);
    };
    
    /**
     * @param {string} prefix
     * @return {number}
     */
    MapSum.prototype.sum = function (prefix) {
        return this.t.search(prefix);
    };
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * var obj = new MapSum()
     * obj.insert(key,val)
     * var param_2 = obj.sum(prefix)
     */
    
    
  • public class Trie {
        private Trie[] children = new Trie[26];
        private int val;
    
        public void Insert(string w, int x) {
            Trie node = this;
            for (int i = 0; i < w.Length; ++i) {
                int idx = w[i] - 'a';
                if (node.children[idx] == null) {
                    node.children[idx] = new Trie();
                }
                node = node.children[idx];
                node.val += x;
            }
        }
    
        public int Search(string w) {
            Trie node = this;
            for (int i = 0; i < w.Length; ++i) {
                int idx = w[i] - 'a';
                if (node.children[idx] == null) {
                    return 0;
                }
                node = node.children[idx];
            }
            return node.val;
        }
    }
    
    public class MapSum {
        private Dictionary<string, int> d = new Dictionary<string, int>();
        private Trie trie = new Trie();
    
        public MapSum() {
        }
    
        public void Insert(string key, int val) {
            int x = val - (d.ContainsKey(key) ? d[key] : 0);
            d[key] = val;
            trie.Insert(key, x);
        }
    
        public int Sum(string prefix) {
            return trie.Search(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);
     */
    
    
  • struct Trie {
        children: Vec<Option<Box<Trie>>>,
        val: i32,
    }
    
    impl Trie {
        fn new() -> Self {
            Trie {
                children: (0..26).map(|_| None).collect(),
                val: 0,
            }
        }
    
        fn insert(&mut self, w: &str, x: i32) {
            let mut node = self;
            for c in w.chars() {
                let idx = (c as usize) - ('a' as usize);
                if node.children[idx].is_none() {
                    node.children[idx] = Some(Box::new(Trie::new()));
                }
                node = node.children[idx].as_mut().unwrap();
                node.val += x;
            }
        }
    
        fn search(&self, w: &str) -> i32 {
            let mut node = self;
            for c in w.chars() {
                let idx = (c as usize) - ('a' as usize);
                if node.children[idx].is_none() {
                    return 0;
                }
                node = node.children[idx].as_ref().unwrap();
            }
            node.val
        }
    }
    
    struct MapSum {
        d: std::collections::HashMap<String, i32>,
        trie: Trie,
    }
    
    impl MapSum {
        fn new() -> Self {
            MapSum {
                d: std::collections::HashMap::new(),
                trie: Trie::new(),
            }
        }
    
        fn insert(&mut self, key: String, val: i32) {
            let x = val - self.d.get(&key).unwrap_or(&0);
            self.d.insert(key.clone(), val);
            self.trie.insert(&key, x);
        }
    
        fn sum(&self, prefix: String) -> i32 {
            self.trie.search(&prefix)
        }
    }
    
    

All Problems

All Solutions