目录

• 题目
• 思路
  • 代码
  • 复杂度分析

题目

677. 键值映射

思路

• 插入就是前缀树的插入
• val值意思是该单词对应的值，而不是该单词每一个字符对应的值（刚开始我以为每个字符的val都要对应该单词的val，其实想错了）
• 获取前缀子串的key总和时候，用 DFS 前序遍历递归来求解，先将 node 指向当前的字串最后一个位置，然后从该位置开始前序遍历，将末尾的 val 相加即为 sum 总和

代码

class MapSum {

    private TrieNode root;
    private int sum;

    public MapSum() {
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        TrieNode node = root;

        for (int i = 0; i < key.length(); i++) {
            if (node.children[key.charAt(i) - 'a'] == null) {
                node.children[key.charAt(i) - 'a'] = new TrieNode();
            }
            node = node.children[key.charAt(i) - 'a'];
        }
        // 不存在的话，在前缀树的单词最后一个字符位置初始该值；若存在，就替换
        node.val = val;
    }
    
    public int sum(String prefix) {
        sum = 0;
        TrieNode node = root;

        // 查看该前缀是否存在
        for (int i = 0; i < prefix.length(); i++) {
            if (node.children[prefix.charAt(i) - 'a'] == null) {
                return sum;
            }
            node = node.children[prefix.charAt(i) - 'a'];
        }
        // 前序遍历，递归计算总和
        getSum(node);
        return sum;
    }

    /**
    * N叉树的前序遍历
    */
    private void getSum(TrieNode node) {
        if (node == null) {
            return;
        }
        sum += node.val;
        for (int i = 0; i < 26; i++) {
            getSum(node.children[i]);
        }
    }

    private class TrieNode {
        int val;
        TrieNode[] children;

        TrieNode() {
            val = 0;
            children = new TrieNode[26];
        }
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)，其中 N 为字符串长度
• 空间复杂度：\(O(26^N)\)