Java Trie + DP Solution. O(len(word)) insert and O(len(prefix)) sum.


  • 0
    A
    import java.util.*;
    
    class MapSum {
    
        private class Trie {
            private class TrieNode {
                Map<Character, TrieNode> links;
                TrieNode parent;
                int childrenSum;
                int value;
    
                public TrieNode() {
                    links = new HashMap<>();
                    value = 0;
                    childrenSum = 0;
                    parent = null;
                }
            }
    
            TrieNode root;
    
            public Trie() {
                root = new TrieNode();
            }
    
            public void insertWord(String word, int value) {
                TrieNode currentNode = root;
                for (int i = 0; i < word.length(); i++) {
                    Character c = word.charAt(i);
                    if (currentNode.links.containsKey(c)) {
                        currentNode = currentNode.links.get(c);
                    } else {
                        TrieNode newNode = new TrieNode();
                        newNode.parent = currentNode;
                        currentNode.links.put(c, newNode);
                        currentNode = newNode;
                    }
                }
                int difference = value - currentNode.value;
                currentNode.value = value;
                while (currentNode != null) {
                    currentNode.childrenSum += difference;
                    currentNode = currentNode.parent;
                }
            }
    
            public int getPrefixSum(String prefix) {
                TrieNode currentNode = root;
                for (int i = 0; i < prefix.length(); i++) {
                    Character c = prefix.charAt(i);
                    if (!currentNode.links.containsKey(c)) {
                        return 0;
                    }
                    currentNode = currentNode.links.get(c);
                }
                return currentNode.childrenSum;
            }
        }
    
        Trie trie;
        
        /** Initialize your data structure here. */
        public MapSum() {
            trie = new Trie();
        }
        
        public void insert(String key, int val) {
            trie.insertWord(key, val);    
        }
        
        public int sum(String prefix) {
            return trie.getPrefixSum(prefix); 
        }
    }
    

Log in to reply
 

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