Trie Solution


  • 0
    C
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        Integer value = null;     
    }
    
    public class MapSum {
        
        //Trie Data Structure
        TrieNode root;
        int sum;
        /** Initialize your data structure here. */
        public MapSum() {
            root = new TrieNode();
            sum = 0; 
        }
        
        public void insert(String key, int val) {
            TrieNode current = root;
            
            for(int i=0;i<key.length();i++){
                int index = key.charAt(i) - 'a';
                if(current.children[index]==null){
                    current.children[index] = new TrieNode();
                }
                current = current.children[index];
            }
            
            current.value = val;
        }
        
        public int sum(String prefix) {
            sum = 0;
            TrieNode current = root;
            
            for(int i=0;i<prefix.length();i++){
                int index = prefix.charAt(i) - 'a';
                if(current.children[index]==null){
                    return 0;
                }
                current = current.children[index];
            }
            dfs(current);
            return sum;
        }
        
        public void dfs(TrieNode root){
            if(root==null){
                return;
            }
            if(root.value!=null){
                sum = sum + root.value;
            }
            for(int i=0;i<26;i++){
                if(root.children[i]!=null){
                    dfs(root.children[i]);
                }
            }
        }
        
        
        
    }
    
    /**
     * 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.