leetcode 677. 键值映射(trie解决)

拼搏现实的明天。 2022-02-22 01:55 165阅读 0赞

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

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

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

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

**思路:**  
这道题可以用map来解决,也可以用trie来解决,用trie解决的思路是,每个节点增加一个属性value,表示对应的值,在对trie进行前缀查询的时候,查询完成就已当前结束的节点开始,依次遍历它下面的节点,把节点的值与当前结束的节点的值(当前节点如果不为终止节点,value默认为0,不影响)相加,最后得出结果.

import java.util.TreeMap;
    
    // leetcode 677. 键值映射
    class MapSum { 
    
        private class Node { 
            public TreeMap<Character, Node> next;
            public int value;
    
            public Node(int value) { 
                this.value = value;
                next = new TreeMap<>();
            }
    
            public Node() { 
                this(0);
            }
        }
    
        Node root;
    
        /** Initialize your data structure here. */
        public MapSum() { 
            root = new Node();
        }
        
        public void insert(String word, int val) { 
            Node cur = root;
            for (int i = 0; i < word.length(); i++) { 
                char c = word.charAt(i);
                if(cur.next.get(c) == null) { 
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            cur.value = val;
        }
        
        public int sum(String prefix) { 
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) { 
                char c = prefix.charAt(i);
                if(cur.next.get(c) == null) { 
                    return 0;
                }
                cur = cur.next.get(c);
            }
            return sum(cur);
        }
    
        private int sum(Node node) { 
            int res = node.value;
            for(char c : node.next.keySet()) { 
                res += sum(node.next.get(c));
            }
            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); */