Java Trie + Map based solution


  • 0
    C

    The solution should be quite easy to understand. Use Trie to record the sum of words with a certain prefix, and a map to look up the values associated with words that have been inserted.

    class MapSum {
        private class Trie {
            Map<Character, Trie> next;
            int sum;
            Trie() {
                next = new HashMap<>();
                sum = 0;
            }
        }
        
        private Trie root;
        private Map<String, Integer> inserted;
        /** Initialize your data structure here. */
        public MapSum() {
            root = new Trie();
            inserted = new HashMap<>();
        }
        
        public void insert(String key, int val) {
            int change = val - inserted.getOrDefault(key, 0);
            root.sum += change;
            Trie walk = root;
            for(char c : key.toCharArray()) {
                if(walk.next.get(c) == null) {
                    walk.next.put(c, new Trie());
                }
                walk = walk.next.get(c);
                walk.sum += change;
            }
            inserted.put(key, val);
        }
        
        public int sum(String prefix) {
            Trie walk = root;
            for(char c : prefix.toCharArray()) {
                if(walk.next.get(c) == null) return 0;
                walk = walk.next.get(c);
            }
            return walk.sum;
        }
    }
    

Log in to reply
 

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