677. 键值映射（Trie）

677. 键值映射

• 题目
• 解题思路
• 代码

题目

实现一个 MapSum 类，支持两个方法，insert 和 sum：

• MapSum() 初始化 MapSum 对象
• void insert(String key, int val) 插入 key-val 键值对，字符串表示键 key ，整数表示值 val 。如果键 key 已经存在，那么原来的键值对将被替代成新的键值对。
• int sum(string prefix) 返回所有以该前缀 prefix 开头的键 key 的值的总和。

提示：

• 1 <= key.length, prefix.length <= 50
• key 和 prefix 仅由小写英文字母组成
• 1 <= val <= 1000
• 最多调用 50 次 insert 和 sum

解题思路

和208题差不多，只不过这题没用利用一个内部类来构造Trie，而是直接构建，所以有了MapSum cur = this;。自己额外建了一个getVal()来帮助解题，其余的没啥说的看代码注释就行了。

代码

    class MapSum {

        int sum; // 前缀对应的和
        MapSum[] children; //子节点
        Integer val; // key对应的val，null表示还没有key


        /**
         * Initialize your data structure here.
         */
        public MapSum() {
            children = new MapSum[26];
            sum = 0;
            val = null;
        }


        // 获取指定key对应的val，key不存在返回null
        public Integer getVal(String key) {
            MapSum cur = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该key在trie中。
                    return null;//没有就返回null
                }
                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            return cur.val;//存在就返回该节点的值
        }

        // 插入(key，val)，更新每个节点val和sum
        public void insert(String key, int val) {
            Integer old = getVal(key);
            if (old == null) { // 不存在key
                old = 0;
            }
            MapSum cur = this;
            for (int i = 0; i < key.length(); i++) {
                char c = key.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有该字符在trie中。
                    cur.children[c - 'a'] = new MapSum();//没有就新建一个
                }

                cur.sum = cur.sum - old + val; // 遍历过程中更新当前节点的sum值，中间节点不更新val
                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            cur.sum = cur.sum - old + val; // 更新最后一个节点的sum值
            cur.val = val; // 更新最后一个节点的val值
        }


        // 查找前缀对应的sum
        public int sum(String prefix) {
            MapSum cur = this;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);//分割出来字符
                //c-'a' 得到的是数字， 比如'a'-'a'=0;'b'-'a'=1;
                if (cur.children[c - 'a'] == null) {//cur节点的[c-'a']下标处没有东西，证明没有key在trie中。
                    return 0;//没有就返回0
                }

                //如果有该节点，那么就要走到该节点去。
                cur = cur.children[c - 'a'];
            }
            return cur.sum; //有就返回这个sum
        }
    }