Optimal Java Solution with TrieTree and HashMap


  • 0
    R
    class MapSum {
        /** Initialize your data structure here. */
        TrieNode root;    
        HashMap <String , Integer> hm;
    
        public MapSum() {
            root = new TrieNode();
            hm = new HashMap<>();
        }
        
        public void insert(String key, int val) {
            if (hm.containsKey(key)){
                int temp = hm.get(key);
                hm.put(key , val);
                val = val - temp;
            } else {
                hm.put(key , val);
            }
            
            TrieNode current = root;
            for (char c : key.toCharArray()){
                if (current.children.containsKey(c)){
                    Pair p = current.children.get(c);
                    p.value += val;
                    current.children.put(c , p);
                } else {
                    Pair p = new Pair();
                    p.value = val;
                    current.children.put(c,p);                
                }
                current = current.children.get(c).next;
            }
        }
        
        public int sum(String prefix) {
            TrieNode current = root;
            int sum = 0;
            for (char c: prefix.toCharArray()){
                if (!current.children.containsKey(c)){
                    return 0;
                }
                sum = current.children.get(c).value;
                current = current.children.get(c).next;
            }
            return sum;
        }
    }
    
    class TrieNode {
        HashMap<Character, Pair> children;
       
        TrieNode() {
            children = new HashMap<>();
        }    
    }
    class Pair{
        int value;
        TrieNode next;
        
        Pair(){
            value = 0;
            next = new TrieNode();
        }
    }
    ```

Log in to reply
 

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