Java Trie Solution


  • 0
    TrieNode root;
    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode current = root;
        for (int i = 0 ; i < key.length(); i++) {
            if (current.children[(int)key.charAt(i)] == null) {
                current.children[(int)key.charAt(i)] = new TrieNode();
            }
            current = current.children[(int)key.charAt(i)];
        }
        current.val = val;
        current.isWord = true;
    }
    
    public int sum(String prefix) {
        if (prefix == null || prefix.length() == 0) return 0;
        TrieNode current = root;
        for (int i = 0; i < prefix.length(); i++) {
            current = current.children[prefix.charAt(i)];
            if (current == null) return 0;
        }
        return dfs(current);
    }
    
    private int dfs (TrieNode current) {
        int sum = 0;
        if (current.isWord) sum += current.val;
        for (int i = 0; i < 256; i++) {
            if (current.children[i]!=null) {
                sum += dfs(current.children[i]);
            }
        }
        return sum;
    }
    class TrieNode {
        boolean isWord;
        TrieNode[] children;
        int val;
        public TrieNode (){
            children = new TrieNode[256];
        }
    }

Log in to reply
 

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