677-键值映射

leetcode 链接：https://leetcode-cn.com/problems/map-sum-pairs/

题目

解法

class MapSum {
    private class TrieNode {
        private static final int size = 26;
        // 存入的值，路径上全为0，到结尾时设置为相应的key的value
        int value;
        // 子元素数组，数组索引0代表'a',索引1代表'b'，以此类推
        TrieNode[] next;
        // 标识，用于减少遍历子元素数组的遍历，只要进行过插入就设置为true
        boolean hasChild;
        public TrieNode(int value) {
            this.value = value;
            this.next = new TrieNode[size];
            this.hasChild = false;
        }
        public TrieNode() {
            this(0);
        }
        public boolean containsKey(char ch) {
            return next[ch - 'a'] != null;
        }
        public TrieNode get(char ch) {
            return next[ch - 'a'];
        }
        public void set(char ch, TrieNode node) {
            hasChild = true;
            next[ch - 'a'] = node;
        }
    }
    // 根元素
    private final TrieNode root;
    /**
     * Initialize your data structure here.
     */
    public MapSum() {
        root = new TrieNode();
    }
    public void insert(String key, int val) {
        TrieNode curr = root;
        for (int i = 0; i < key.length(); i++) {
            char ch = key.charAt(i);
            // 如果当前位置没有元素，则进行set
            if (!curr.containsKey(ch)) {
                curr.set(ch, new TrieNode());
            }
            curr = curr.get(ch);
        }
        // 不管当前位置是否有值，均进行覆盖更新
        curr.value = val;
    }
    public int sum(String prefix) {
        TrieNode curr = root;
        // 循环到前缀的最后一个节点
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            // 如果前缀不匹配，则返回0
            if (!curr.containsKey(ch)) {
                return 0;
            }
            curr = curr.get(ch);
        }
        return cal(curr);
    }
    // 递归进行求值，路径上的元素皆为0，遍历上将路径上的值全部加上即可
    private int cal(TrieNode curr) {
        // 到达末尾，当前元素没有子元素，返回节点值
        if (!curr.hasChild) {
            return curr.value;
        }
        int sum = curr.value;
        // 遍历求和
        for (TrieNode trieNode : curr.next) {
            if (trieNode != null) {
                sum += cal(trieNode);
            }
        }
        return sum;
    }
}