Java Trie based solution


  • 0

    Having a trie for the Map keys fits perfectly, as its easy to maintain prefix sum. Every time we insert a key, we make sure to update the sum of all the nodes in the path. If the key to be inserted is already present, then we update all the nodes in the path, by decreasing the old value of the key and adding the new value.

    class MapSum {
    
        Trie trie;
        /** Initialize your data structure here. */
        public MapSum() {
            trie = new Trie(256);
        }
    
        public void insert(String key, int val) {
            trie.insert(key, val);
        }
    
        public int sum(String prefix) {
            int sum = trie.getPrefixSum(prefix);
            return sum == Integer.MAX_VALUE ? 0 : sum;
        }
    
        class Trie {
            private int R;
            private TrieNode root;
    
            public Trie(int R) {
                this.R = R;
                root = new TrieNode(0);
            }
    
            // Inserts a word into the trie.
            public void insert(String word, int newsum) {
                insert(root, word, exists(word) ? getPrefixSum(word) : 0, newsum);
            }
    
            private void insert(TrieNode root, String word, int oldsum, int newsum) {
                if (word.isEmpty()) { root.isWord = true; return; }
                if (root.next[word.charAt(0)] == null) root.next[word.charAt(0)] = new TrieNode(newsum); else root.next[word.charAt(0)].sum += (newsum-oldsum);
                insert(root.next[word.charAt(0)], word.substring(1), oldsum, newsum);
            }
    
            // Returns the sum, if the word is in the trie.
            public int getPrefixSum(String word) {
                return getPrefixSum(root, word);
            }
    
            private int getPrefixSum(TrieNode root, String word) {
                if(root == null)
                    return Integer.MAX_VALUE;
                if(word.isEmpty())
                    return root.sum;
                return getPrefixSum(root.next[word.charAt(0)], word.substring(1));
            }
    
            // Returns the sum, if the word is in the trie.
            public boolean exists(String word) {
                return exists(root, word);
            }
    
            private boolean exists(TrieNode root, String word) {
                if(root == null) return false;
                if(word.isEmpty())
                    return root.isWord;
                return exists(root.next[word.charAt(0)], word.substring(1));
            }
    
            private class TrieNode {
                private TrieNode[] next = new TrieNode[R];
                private boolean isWord;
                private int sum;
    
                public TrieNode(int sum) {
                    this.sum = sum;
                }
            }
    
        }
    }
    	
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.