AC JAVA Solution using Trie and HashMap


  • 0
    J

    The idea is to use Trie as a dictionary for insertion and search. By using hashmap to keep track of word inserted and the corresponding values.
    Val is stored at every single TrieNode.

    class MapSum {
        TrieNode trie;
        Map<String, Integer> map;
        /** Initialize your data structure here. */
        public MapSum() {
            trie = new TrieNode(' ');
            map = new HashMap<>();
        }
        
        public void insert(String key, int val) {
            if(key == null || key.length() == 0) return;
            TrieNode node = trie;
            if (!map.containsKey(key)) {
                map.put(key, val);
                for (int i = 0; i < key.length(); i++) {
                    int idx = key.charAt(i) - 'a';
                    if (node.children[idx] == null) {
                        node.children[idx] = new TrieNode(key.charAt(i));
                        node.children[idx].num = val;
                    }
                    else {
                        node.children[idx].num += val; 
                    }
                    node = node.children[idx];
                }
            }
            else {
                if (map.get(key) == val) return;
                for (int i = 0; i < key.length(); i++) {
                    node.children[key.charAt(i) - 'a'].num += val - map.get(key);
                    node = node.children[key.charAt(i) - 'a'];
                }
                map.put(key, val);
            }
        }
        
        public int sum(String prefix) {
            if (prefix == null || prefix.length() == 0) return 0;
            TrieNode node = trie;
            for (int i = 0; i < prefix.length(); i++) {
                int idx = (prefix.charAt(i) - 'a');
                if (node.children[idx] == null) {
                    return 0;
                }
                node = node.children[idx];
            }
            return node.num;
        }
    }
    
    class TrieNode {
        TrieNode[] children = new TrieNode[26];
        char val;
        TrieNode(char c) {val = c;}
        int num;
    }
    

  • 0
    C

    @jun1013
    good solution. Just wonder is there any way without using a map? Thanks.


Log in to reply
 

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