Java Pure Trie Solution


  • 0

    As the problem did not restrict the characters of the input string, I used HashMap for TrieNode's children list.

    class MapSum {
    
        /** Initialize your data structure here. */
        public static class TrieNode {
    		Map<Character, TrieNode> children;
    		int sum;
            int val;
    		public TrieNode() {
    			children = new HashMap<>();
                sum = 0;
                val = 0;
    		}
    	}
    
        private TrieNode root;
        public MapSum() {
            root = new TrieNode();
        }
        
        public void insert(String key, int val) {
            int oldValue = findValue(key);
            int delta = val - oldValue;
            TrieNode node = root;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
                node.sum += delta;
            }
            node.val = val;
        }
        
        public int findValue(String key) {
            TrieNode node = root;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);
                if (!node.children.containsKey(c)) {
                    return 0;
                }
                node = node.children.get(c);
            }
            return node.val;
        }
        
        public int sum(String prefix) {
            TrieNode node = root;
            int n = prefix.length();
            for (int i = 0; i < n; i++) {
                char c = prefix.charAt(i);
                if (!node.children.containsKey(c)) return 0;
                node = node.children.get(c);
            }
            return node.sum;
        }
    }
    

Log in to reply
 

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