Java Trie based solution, easy to understand


  • 0
    N
    class MapSum {
        class TrieNode{
            TrieNode [] children;
            int sum;
            TrieNode(){
                children = new TrieNode[26];
                sum=0;
            }
        }
        HashMap<String,Integer> hmap;
        /** Initialize your data structure here. */
       
        TrieNode root = new TrieNode();
        public void insert(String s,int val,int oldVal){
            TrieNode n = root;
            for(char c:s.toCharArray()){
                int index = c-'a';
                if(n.children[index]==null)
                {
                    n.children[index] = new TrieNode();
                }
                n = n.children[index];
                n.sum-=oldVal;
                n.sum+=val;
            }
        }
        
        public int getVal(String s){
            TrieNode n = root;
            for(char c:s.toCharArray()){
                int index = c-'a';
                if(n.children[index]==null)
                    return 0;
                
                n = n.children[index];
            }
            return n.sum;
        }
      
        public MapSum() {
            hmap = new HashMap<String,Integer>();
        }
        
        public void insert(String key, int val) {
            if(!hmap.containsKey(key))
                insert(key,val,0);
            else
                insert(key,val,hmap.get(key));
        hmap.put(key,val);    
        }
        
        public int sum(String prefix) {
            return getVal(prefix);
        }
    }
    

Log in to reply
 

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