AC Trie & BFS


  • 0
    R
    class MapSum {
    
        Trie root;
        
        /** Initialize your data structure here. */
        public MapSum() {
            root = new Trie();
        }
        
        public void insert(String key, int val) {
            Trie currNode = root;
            for (char c:key.toCharArray()) {
                if (currNode.child[c - 'a'] == null) {
                    currNode.child[c - 'a'] = new Trie();
                }
                currNode = currNode.child[c - 'a'];
            }
            
            currNode.isWord = true;
            currNode.val = val;
            
        }
        
        public int sum(String prefix) {
            Trie currNode = root;
            LinkedList<Trie> queue = new LinkedList(); 
            for (char c:prefix.toCharArray()) {
                if (currNode.child[c - 'a'] == null) {
                    return 0;
                }
                currNode = currNode.child[c - 'a'];
            }
            
            int res = 0;
            queue.offer(currNode);
            while (!queue.isEmpty()) {
                Trie curr = queue.poll();
                if (curr.isWord) res += curr.val;
                for (int i=0; i<26; i++) {
                    if (curr.child[i] != null) {
                        queue.offer(curr.child[i]);
                    }
                }
            }
            return res;
        }
        
        class Trie {
            Trie[] child; 
            boolean isWord; 
            int val;
            
            public Trie() {
                child = new Trie[26];
            }
        }
    }
    

Log in to reply
 

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