Java实现 LeetCode 677 键值映射（字典树）

悠悠 2023-07-22 03:53 5阅读 0赞

## 677. 键值映射 ##

实现一个 MapSum 类里的两个方法，insert 和 sum。

对于方法 insert，你将得到一对（字符串，整数）的键值对。字符串表示键，整数表示值。如果键已经存在，那么原来的键值对将被替代成新的键值对。

对于方法 sum，你将得到一个表示前缀的字符串，你需要返回所有以该前缀开头的键的值的总和。

示例 1:

输入: insert("apple", 3), 输出: Null
    输入: sum("ap"), 输出: 3
    输入: insert("app", 2), 输出: Null
    输入: sum("ap"), 输出: 5

class MapSum { 
      class TrieNode{ 
            TrieNode[] children;
            int count;
            public TrieNode(){ 
                this.children = new TrieNode[26];
                count=0;
            }
        } 
        TrieNode root;
        public MapSum() { 
            root = new TrieNode();
        }
        
        public void insert(String key, int val) { 
            TrieNode cur = root;
            for(char c:key.toCharArray()){ 
                if(cur.children[c-'a']==null){ 
                    cur.children[c-'a'] = new TrieNode();
                } 
                cur = cur.children[c-'a'];
            }
            cur.count=val;
        }
        
        public int sum(String prefix) { 
            TrieNode cur = root;
            int res=0;
            for(char c:prefix.toCharArray()){ 
                if(cur.children[c-'a']==null)
                    return 0;
                cur = cur.children[c-'a'];
            }
            res=getSum(cur);
            return res;
        }
        public int getSum(TrieNode root){ 
            int res=root.count;
            for(int i=0;i<26;i++){ 
                if(root.children[i]!=null){ 
                    res+=getSum(root.children[i]);
                }
            }
            return res;
        }
    }
    
    /** * Your MapSum object will be instantiated and called as such: * MapSum obj = new MapSum(); * obj.insert(key,val); * int param_2 = obj.sum(prefix); */