Simple Trie based Java solution.


  • 0
    2
    class MapSum {
        // Trie Node class
        class Node {
            char c;
            HashMap<Character, Node> children;
            boolean isLeaf;
            int val;
            Node(char c) {
                this.c = c;
                children = new HashMap<Character, Node>();
                isLeaf = false;
                val = 0;
            }
        }
        
        Node root;
        
        /** Initialize your data structure here. */
        public MapSum() {
            root = new Node('*');
        }
        // Similar to insert in Trie Node, but this time also save the value
        public void insert(String key, int val) {
            int len = key.length();
            if(len==0) return;
            
            Node curr = root;
            
            for(int i=0; i<len; i++) {
                char ch = key.charAt(i);
                if(!curr.children.containsKey(ch)) {
                    curr.children.put(ch, new Node(ch));
                }
                curr = curr.children.get(ch);
            }
            curr.isLeaf = true;
            curr.val = val;
        }
        
        
        public int sum(String prefix) {
            int sum = 0;
            int len = prefix.length();
            if(len==0) return 0;
            Node curr = root;
            
            for(int i=0; i<len; i++) {
                char ch = prefix.charAt(i);
                if(curr.children.containsKey(ch)) {
                    curr = curr.children.get(ch);
                }
                else {
                    curr = null;
                    break;
                }
            }
            // prefix not found, return zero
            if(curr == null) return 0;
            
            // perform dfs, add all values along the way
            Stack<Node> stack = new Stack<Node>();
            stack.push(curr);
            while(!stack.empty()) {
                Node n = stack.pop();
                sum += n.val;
                for(Node child: n.children.values())
                    stack.push(child);
            }
            return sum;
        }
    }
    
    /**
     * Your MapSum object will be instantiated and called as such:
     * MapSum obj = new MapSum();
     * obj.insert(key,val);
     * int param_2 = obj.sum(prefix);
     */
    

Log in to reply
 

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