【Day 74 】2021-11-22 - 677. 键值映射

[azl397985856]

677. 键值映射

入选理由

暂无

题目地址

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

前置知识

• 哈希表
• Trie
• DFS

  题目描述

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

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

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

示例 1:

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

[yanglr]

思路:

使用哈希表即可。

代码:

实现语言: C++

class MapSum {
    unordered_map<string, int> dict;
public:
    /** Initialize your data structure here. */
    MapSum() {
    }

    void insert(string key, int val) {
        if (dict.count(key) == 0)
            dict[key] = val;
        else dict[key] = val;
    }

    int sum(string prefix) {
        int sum = 0;
        for (auto& kvp : dict)
        {
            if (kvp.first.find(prefix) != string::npos && kvp.first.find(prefix) == 0) /* 需要是前缀, 而不仅仅是子串 */
                sum += kvp.second;
        }
        return sum;
    }
};

复杂度分析:

• 时间复杂度: insert: O(1), sum: O(N), 其中N是哈希表的size
• 空间复杂度: O(N)

[a244629128]

/**
 * Initialize your data structure here.
 */
var MapSum = function () {
  this.trie = {}
};

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function (key, val) {
  let t = this.trie
  for (let char of key) {
    if (!t[char]) t[char] = {}
    t = t[char]
  }
  t['value'] = val
  return null
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
  let t = this.trie
  for (let char of prefix) {
    t = t[char]
    if (!t) return 0
  }
  return sum(t)
  function sum(obj) {
    let rtn = 0
    for (let k in obj) {
      if (k === 'value') rtn += obj[k]
      else rtn += sum(obj[k])
    }
    return rtn
  }
};

[ZacheryCao]

Idea:

Trie

Code:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0
        self.sum = 0
        self.val = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        pre, _, count = self.search(key)
        root = self.root
        for ch in key:
            if ch not in root.children:
                root.children[ch] = TrieNode()
            root = root.children[ch]
            root.sum = root.sum - pre*count + val
        root.count = 1
        root.val = val

    def sum(self, prefix: str) -> int:
        return self.search(prefix)[1]

    def search(self, key):
        root = self.root
        for ch in key:
            if ch not in root.children:
                return 0, 0, 0
            root = root.children[ch]
        return root.val, root.sum, root.count

Complexity

Time: O(N). The largest time complexity is insert. It costs O(N). N is the total length of keys need to be inserted. For search, it's O(M) M is the length of the prefix Space: O(K). K is the total amount of chars that are not shared among all inserted keys.

[zhy3213]

思路

字典树+终点及路径标记，并保证插入时只遍历一次 测试用例太水了，竟然让暴力枚举计算总和速度更快，无语子。

代码

from collections import defaultdict
class MapSum:

    def __init__(self):
        self.tree=defaultdict(int)

    def insert(self, key: str, val: int) -> None:
        tmp=self.tree
        memo=[]
        index=0
        for i in key:
            if i not in tmp:
                break
            tmp=tmp[i]
            memo.append(tmp)
            index+=1
        if index==len(key) and tmp['*']:
            prev=tmp['*']
            for i in memo:
                i['#']+=val-prev
            tmp['*']=val
            return
        for i in memo:
            i['#']+=val
        for i in range(index,len(key)):
            tmp[key[i]]=defaultdict(int)
            tmp=tmp[key[i]]
            tmp['#']+=val
        tmp['*']=val

    def sum(self, prefix: str) -> int:
        tmp=self.tree
        for i in prefix:
            if i not in tmp:
                return 0
            tmp=tmp[i]
        return tmp['#']

[florenzliu]

Explanation

For TrieNode:

• presum: the sum of the values whose keys have the same prefix till the current TrieNode
• children: a dictionary

For Trie:

• root: the root of a tree
• map: a hashmap of key-value pair

Python

class TrieNode:
    def __init__(self):
        self.presum = 0
        self.children = {}

class MapSum:

    def __init__(self):
        self.map = {}
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map[key] if key in self.map else val
        self.map[key] = val
        node = self.root

        for ch in key:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node.children[ch].presum += delta
            node = node.children[ch]        

    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]
        return node.presum

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

Complexity:

• Time Complexity: O(K) where K is the length of the key
• Space Complexity: O(n) where n is the size of the total input

[wangzehan123]

题目地址(677. 键值映射)

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

题目描述

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

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

 

示例：

输入：
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
输出：
[null, null, 3, null, 5]

解释：
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);  
mapSum.sum("ap");           // return 3 (apple = 3)
mapSum.insert("app", 2);    
mapSum.sum("ap");           // return 5 (apple + app = 3 + 2 = 5)

 

提示：

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

前置知识

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class MapSum {
    TreeNode root =new TreeNode();

    public MapSum() {

    }

    public void insert(String key, int val) {
        TreeNode treeNode = root;
        Queue<TreeNode> que =new ArrayDeque<>();
        int last = 0;
        for(char c : key.toCharArray()){
          TreeNode  nextNode  = treeNode.findNext(c);
            if(nextNode != null){
                que.offer(nextNode);
                treeNode = nextNode;
            }else{
                treeNode =  treeNode.putNext(c,val);
            }
        }
        if(treeNode.end){
            last = treeNode.endVal;
        }
        while(!que.isEmpty()){
           TreeNode tn  = que.poll();
            tn.val +=  (val-last);
        }
        treeNode.end = true;
        treeNode.endVal = val;
    }

    public int sum(String prefix) {
        TreeNode treeNode = root;
        for(char c: prefix.toCharArray()){
            if(treeNode == null){
                return 0 ;
            }
            treeNode = treeNode.findNext(c);
        }
        return treeNode==null?0:treeNode.val;
    }

    public static class TreeNode{
        int val;
        boolean end = false;
        int endVal = 0;
        char c;
        TreeNode[] charArrays = new TreeNode[26];
        public void put(char c,int val){
            this.c = c;
            this.val=val;
            this.endVal = val;
        }

        public TreeNode putNext(char c,int val){
            TreeNode treeNode =  charArrays[c -'a'];
            if(treeNode ==null){
                treeNode = new TreeNode();
                treeNode.put(c,val);
                charArrays[c -'a'] = treeNode;
            }else{
                treeNode.val+=val;
            }
            return treeNode;
        }
        public TreeNode findNext(char c){
            return charArrays[c-'a'];
        }

    }

}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[thinkfurther]

思路

构成一个trie，然后用dfs搜索

代码

class Node:
    def __init__(self):
        self.children = {}
        self.presum = 0

class MapSum:

    def __init__(self):
        self.root = Node()
        self.sum_result = 0

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for ch in key:
            if ch not in node.children:
                node.children[ch] = Node()
            node = node.children[ch]
        node.presum = val

    def sum(self, prefix: str) -> int:
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return 0
            node = node.children[ch]

        self.dfs(node)
        sum_result , self.sum_result = self.sum_result, 0
        return sum_result

    def dfs(self, node):
        if node.presum:
            self.sum_result += node.presum

        for ch in node.children:
            self.dfs(node.children[ch])

[yachtcoder]

class TrieNode:
    def __init__(self):
        self.children = defaultdict(TrieNode)
        self.val = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for c in key:
            node = node.children[c]
        node.val = val

    def dfs(self, node):
        #traverse n-ary tree
        if not node: return 0
        ret = node.val
        for c,node in node.children.items():
            ret += self.dfs(node)
        return ret

    def sum(self, prefix: str) -> int:
        node = self.root
        ret = 0
        for c in prefix:
            node = node.children[c]
        ret = self.dfs(node)
        return ret

[zhangzz2015]

思路

• 用Trie数据结构比较方便找到prefix开始的string。因为需要求prefix开始所有string对应的val 和，同时相同val 插入会冲掉。同时利用hash map 维护 key - > val 对应，当有相同的key ，我们可计算出delta ，更新trie 中对应字符串所有的number

关键点

代码

• 语言支持：C++

C++ Code:

struct trieNode 
{
    vector<trieNode*> child; 
    int number; 

    trieNode()
    {
       child.resize(26);  
       number =0; 
    }; 

}; 

class MapSum {
public:
    trieNode* rootNode; 
    unordered_map<string, int> record; 
    MapSum() {

      rootNode = new trieNode; 

    }

    void insert(string key, int val) {
        trieNode* current = rootNode; 
        if(record.count(key))
        {
           int delta = val - record[key] ; 
           for(int i=0; i< key.size(); i++)
           {
               int index = key[i] - 'a'; 
               current = current->child[index]; 
               current->number += delta; 
           }
           record[key] = val;  
        }
        else
        {
           for(int i=0; i< key.size(); i++)
           {
               int index = key[i] - 'a'; 
               if(current->child[index]==NULL)
               {
                   current->child[index] = new trieNode; 
               }
               current->child[index]->number += val;                

               current = current->child[index];     
           }
           record[key] = val;  
        }
    }

    int sum(string prefix) {
        trieNode * current = rootNode; 
        for(int i=0; i< prefix.size(); i++)
        {
            int index = prefix[i] - 'a';
            if(current->child[index] == NULL)
            {
                return 0; 
            }
            current = current->child[index]; 
        }

        return current->number; 

    }
};

[yingliucreates]

link:

https://leetcode.com/problems/map-sum-pairs/

代码 Javascript

const MapSum = function () {
  this.map = {};
};

MapSum.prototype.insert = function (key, val) {
  this.map[key] = val;
};

MapSum.prototype.sum = function (prefix) {
  return Object.keys(this.map)
    .filter((key) => key.startsWith(prefix))
    .map((key) => this.map[key])
    .reduce((total, curr) => total + curr, 0);
};

[JiangyanLiNEU]

Python

class Trie():
    def __init__(self):
        self.child = {}
        self.sum = 0
        self.wordEnd = False

class MapSum(object):
    def __init__(self):
        self.trie = Trie()
    def insert(self, key, val):
        cur = self.trie
        for k in key:
            if k not in cur.child:
                cur.child[k] = Trie()
            cur = cur.child[k]
        cur.sum = val
        cur.wordEnd = True
    def sum(self, prefix):
        cur = self.trie
        for p in prefix:
            if p not in cur.child:
                return 0
            cur = cur.child[p]
        def cal(tree):
            result = 0
            if tree.wordEnd:
                 result += tree.sum
            for child in tree.child:
                result += cal(tree.child[child])
            return result
        return cal(cur)

JavaScript

var Trie = function(){
    this.wordEnd = false;
    this.child = new Map();
    this.summ = 0;
}
var MapSum = function() {
    this.trie = new Trie();
};
MapSum.prototype.insert = function(key, val) {
    let cur = this.trie;
    for (let k of key){
        if (cur.child.has(k)===false){cur.child.set(k, new Trie())};
        cur = cur.child.get(k);
    };
    cur.wordEnd = true;
    cur.summ = val;
};

MapSum.prototype.sum = function(prefix) {
    let cur = this.trie;
    let valid = true;
    for (let p of prefix){
        if (cur.child.has(p)){
            cur = cur.child.get(p);
            continue;
        }else{
            valid = false;
            break;
        };
    };
    if (valid === false){return 0}
    else{
        var cal = function(trie){
            let result = 0;
            if (trie.wordEnd === true){result += trie.summ};
            trie.child.forEach((value, key) => {result += cal(value)});
            return result;
        };
        return cal(cur);
    }
};

[CoreJa]

思路

和昨天的Trie前缀树一样，可直接套用西法的板子，不过要注意两个点：

• 题目中的sum变成了某个val，所以不再是累加1而是每个字符节点累加val
• 题目要求如果字符串已存在，则将其替换成新的val
  • 这个要求则需要我们额外存储字符串对应的val，这样在insert操作时可以减掉原先的val
  • 有两个方法实现，
  • 在单词结束的字符里存对应的val，那每次插入前就需要先确认这个词是否存在(遍历两遍)
  • 单独使用一个哈希表来存放字符串以及对应的val，插入前通过O(1)的复杂度确认单词是否存在

代码

class TrieNode:
    def __init__(self):
        self.pre_sum = 0
        self.children: Dict[str, TrieNode] = {}

class MapSum:
    def __init__(self):
        self.key = {}
        self.root = TrieNode()

    def search(self, key) -> TrieNode:
        cur = self.root
        for ch in key:
            if ch not in cur.children:
                return TrieNode()
            cur = cur.children[ch]
        return cur

    def insert(self, key: str, val: int) -> None:
        pre_val = self.key[key] if key in self.key else 0
        self.key[key] = val

        cur = self.root
        for ch in key:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
            cur.pre_sum += val - pre_val

    def sum(self, prefix: str) -> int:
        return self.search(prefix).pre_sum

[biancaone]

class TrieNode:
    def __init__(self):
        self.children = collections.defaultdict(TrieNode) 
        self.amount = 0

class MapSum:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for c in key:
            node = node.children[c]
        node.amount = val

    def dfs(self, node, res):
        res[0] += node.amount
        for n in node.children.values():
            self.dfs(n, res)

    def sum(self, prefix: str) -> int:
        node = self.root
        res = [0]
        for c in prefix:
            if c not in node.children: 
                return 0
            node = node.children[c]

        self.dfs(node, res)
        return res[0]

[pophy]

思路

• 用TrieNode保存key和val
• 利用dfs找到所有key 前缀是prefix的node，并计算sum

Java Code

class MapSum {
    Trie trie = new Trie();
    public MapSum() {
    }
    public void insert(String key, int val) {
        trie.insert(key, val);
    }
    public int sum(String prefix) {
        return trie.getSumByPrefix(prefix);
    }
}
class Trie {
    TrieNode root = new TrieNode();
    public void insert(String word, int val) {
        TrieNode p = root;
        for (char c : word.toCharArray()) {
            if (p.children.get(c) == null) {
                p.children.put(c, new TrieNode());
            }
            p = p.children.get(c);
        }
        p.isWord = true;
        p.val = val;
    }
    public boolean searchPrefix(String prefix) {
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            if (p.children.get(c) == null) {
                return false;
            }
            p = p.children.get(c);
        }
        return true;
    }
    public int getSumByPrefix(String prefix) {
        int sum = 0;
        TrieNode p = root;
        for (char c : prefix.toCharArray()) {
            if (p.children.get(c) == null) {
                return 0;
            }
            p = p.children.get(c);
        }
        List<Integer> vals = new ArrayList<>();
        helper(p, vals, new StringBuilder(prefix));
        return vals.stream().mapToInt(Integer::intValue).sum();
    }
    private void helper(TrieNode root, List<Integer> vals, StringBuilder prefix) {
        if (root.isWord) {
            vals.add(root.val);
        }
        if (!searchPrefix(prefix.toString())) {
            return;
        }
        for (char c : root.children.keySet()) {
            prefix.append(c);
            helper(root.children.get(c), vals, prefix);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }
    private static class TrieNode {
        Map<Character, TrieNode> children = new HashMap<>();
        int val = 0;
        boolean isWord = false;
    }
}

[chenming-cao]

解题思路

前缀树+哈希表。建立前缀树记录和查询相应前缀出现的总数sum。因为键值对的key已经存在，我们需要将原来键值对更新为新的键值对，所以该键key所有可能的前缀树都要进行更新。更新时我们需要该键key之前的值，还有现在的值，之前的值可以通过前缀树的search方法找到，但是时间复杂度为O(len(key))，我们还可以通过哈希表查询，只需要O(1)。这里使用哈希表存储键值对。在insert方法中，我们要从哈希表中找到之前的值，更新哈希表，同时更新前缀出现的次数，每个前缀都加上val - pre。在sum方法中，我们使用前缀树中查前缀的方法即可，返回precount即为结果。

代码

class MapSum {

    private class TrieNode {
        TrieNode[] children;
        int precount;
        public TrieNode() {
            children = new TrieNode[26];
            precount = 0;
        }
    }

    TrieNode root;
    Map<String, Integer> map;

    public MapSum() {
        root = new TrieNode();
        map = new HashMap<>();
    }

    public void insert(String key, int val) {
        int pre = 0;
        // find the previous val to this key, will use the previous val to update precount
        if (map.containsKey(key)) {
            pre = map.get(key);
        }
        // update HashMap with the new key-val pair
        map.put(key, val);
        // update precount for all possible prefix
        TrieNode node = root;
        for (int i = 0; i < key.length(); i++) {
            char letter = key.charAt(i);
            if (node.children[letter - 'a'] == null) {
                node.children[letter - 'a'] = new TrieNode();
            }
            node = node.children[letter - 'a'];
            node.precount += val - pre;
        }
    }
    // search precount
    public int sum(String prefix) {
        TrieNode node = root;
        for (int i = 0; i < prefix.length(); i++) {
            char letter = prefix.charAt(i);
            if (node.children[letter - 'a'] == null) {
                node.children[letter - 'a'] = new TrieNode();
            }
            node = node.children[letter - 'a'];
        }
        return node.precount;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

复杂度分析

• 时间复杂度：insert和sum均为O(n)，n为相应的字符串的长度
• 空间复杂度：O(m^n)，m为字符集大小，此题为26，n为字符串长度

[kidexp]

thoughts

用trie来构建。对于sum对tire做一次dfs

code

class TrieNode:
    def __init__(self) -> None:
        self.children = {}
        self.val = 0

class MapSum:
    def __init__(self):
        self.trie = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.trie
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.val = val

    def sum(self, prefix: str) -> int:
        sum_ = 0

        def compute_sum(node):
            if node.val:
                nonlocal sum_
                sum_ += node.val
            if node.children:
                for char in node.children:
                    compute_sum(node.children[char])

        node = self.trie
        for char in prefix:
            if char in node.children:
                node = node.children[char]
            else:
                return 0
        compute_sum(node)
        return sum_

complexity

Time: Insert O(n) n 为key的长度, Sum O(m) m是tire沿着prefix的subtree有多少个节点

Space: O(t*n) t为key的个数， n为key的长度

[vincentLW]

class TrieNode:
    def __init__(self):
        self.children = {}
        self.count = 0
        self.sum = 0
        self.val = 0

class MapSum:

    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        pre, _, count = self.search(key)
        root = self.root
        for ch in key:
            if ch not in root.children:
                root.children[ch] = TrieNode()
            root = root.children[ch]
            root.sum = root.sum - pre*count + val
        root.count = 1
        root.val = val

    def sum(self, prefix: str) -> int:
        return self.search(prefix)[1]

    def search(self, key):
        root = self.root
        for ch in key:
            if ch not in root.children:
                return 0, 0, 0
            root = root.children[ch]
        return root.val, root.sum, root.count

[yan0327]

思路： 看完这题之后，果然应该把trieNode单独拆成一个结构体放在总需求里面。 因为考虑到映射总和这部分会影响trieNode的正常使用，因此有必要拆开来。 这题与普通trie的区别就在于，需要对前缀计数。 因此在构造的时候要比较当前string的val是否大于映射值的val，若大于的话，要减去差值 同时降val给到hash表 【关键是处理部分】

type TrieNode struct{
    children [26]*TrieNode
    val int
}

type MapSum struct {
    root *TrieNode
    count map[string]int
}

func Constructor() MapSum {
    return MapSum{&TrieNode{},map[string]int{}}
}

func (this *MapSum) Insert(key string, val int)  {
    x := val
    if this.count[key] > 0{
        x -= this.count[key]
    }
    this.count[key] = val
    node := this.root
    for _,ch := range key{
        ch -= 'a'
        if node.children[ch] == nil{
            node.children[ch] = &TrieNode{}
        }
        node = node.children[ch]
        node.val += x
    }
}

func (this *MapSum) Sum(prefix string) int {
    node := this.root
    for _,ch := range prefix{
        ch -= 'a'
        if node.children[ch] == nil{
            return 0
        }
        node = node.children[ch]
    }
    return node.val
}

时间复杂度：O（N）插入搜索都是搜一个字符串长度 空间复杂度：O（NMC）

[liuyangqiQAQ]

字典树

class MapSum {

    MapSum[] children;

    int val;

    public MapSum() {
        children = new MapSum[26];
    }

    public void insert(String key, int val) {
        if(key.length() == 0) return;
        MapSum cur = this;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            int index = c - 'a';
            if(cur.children[index] == null) {
                cur.children[index] = new MapSum();
            }
            cur = cur.children[index];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        //找到当前对应的值
        MapSum cur = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if(cur.children[index] == null) {
                return 0;
            }else {
                cur = cur.children[index];
            }
        }
        return dfs(cur) + cur.val;
    }

    public int dfs(MapSum cur) {
        int res = 0;
        MapSum[] children = cur.children;
        for (int i = 0; i < children.length; i++) {
            if(children[i] != null) {
                res += children[i].val;
                res += dfs(children[i]);
            }
        }
        return res;
    }

}

[joeytor]

思路

使用 Trie 的数据结构

每次 insert 将前缀加入 Trie, 并且将 val 存储到这个 Trie node 中

sum 时先找到对应的 Trie node, 如果没有返回 0, 如果找到了 Trie node, 那么在这个 Trie node 开始 dfs, 将所有后面的方案都加入 count, 中, 并返回 count

也可以在 insert 的时候将 val 加入每一个经过的 Trie node 中, 再用一个 map 记录 key, val 的值, 这样如果 key 已经存在了, 那么每次加入的值就是 val - old_val, 这样 sum 的时候只要直接读取 Trie node 中 sum 的值即可

from collections import defaultdict
class Trie:
    def __init__(self):
        self.trie = dict()
        self.endWord = ''
        self.val = 0

    def insert(self, word, val):
        node = self
        for ch in word:
            if ch not in node.trie:
                node.trie[ch] = Trie()
            node = node.trie[ch]
        if node.endWord == word:
            node.val = val
        else:
            node.endWord = word
            node.val = val

    def search(self, prefix):
        node = self
        for ch in prefix:
            if ch not in node.trie:
                return -1
            else:
                node = node.trie[ch]
        return node

class MapSum:

    def __init__(self):
        self.trie_root = Trie()

    def insert(self, key: str, val: int) -> None:
        self.trie_root.insert(key, val)

    def sum(self, prefix: str) -> int:

        def dfs(node):
            count = 0
            if node.endWord != '':
                count += node.val
            for ch in node.trie:
                count += dfs(node.trie[ch])
            return count

        node = self.trie_root.search(prefix)
        if node == -1:
            return 0
        else:
            return dfs(node)

# Your MapSum object will be instantiated and called as such:
# obj = MapSum()
# obj.insert(key,val)
# param_2 = obj.sum(prefix)

复杂度

n 为 key 的长度, m 为前缀树中元素个数

时间复杂度: insert O(n) sum 时间复杂度为 O(m+n) O(m) 为 dfs 最坏的复杂度, 需要遍历每一个节点, O(n) 为查询节点的复杂度

空间复杂度: O(m) Trie 的空间复杂度

[okbug]

使用哈希表并且利用startsWith的API去实现

class MapSum {
    constructor() {
        this.map = new Map();
    }

    insert(key, val) {
        const { map } = this;
        map.set(key, val);
    }

    sum(prefix) {
        const { map } = this
        let res = 0;
        for (let [s, v] of map) {
            if (s.startsWith(prefix)) {
                res += v;
            }
        }

        return res;
    }
}

/** 
 * @param {string} prefix
 * @return {number}
 */

[lxy030988]

思路

• 将值存到 map 中
• 如果键值包含给定的前缀，则我们将其值进行相加，返回所有符合要求的值的和。

代码 js

var MapSum = function () {
  this.map = new Map()
}

MapSum.prototype.insert = function (key, val) {
  this.map.set(key, val)
}

MapSum.prototype.sum = function (prefix) {
  let res = 0
  for (const s of this.map.keys()) {
    if (s.startsWith(prefix)) {
      res += this.map.get(s)
    }
  }
  return res
}

复杂度分析

• 时间复杂度：insert O(1) sum O(NM)
• 空间复杂度：O(NM)

[ysy0707]

思路：数组+trie

class MapSum {
    //还有一种哈希表的方法
    private TrieNode root;
    private class TrieNode{
        int val;
        TrieNode[] next = new TrieNode[26];
    }
    /** Initialize your data structure here. */
    public MapSum() {
        root = new TrieNode();
    }

    public void insert(String key, int val) {
        TrieNode node = root;
        for(char c: key.toCharArray()){
            int i = c - 'a';
            if(node.next[i] == null){
                node.next[i] = new TrieNode();
            }
            node = node.next[i];
        }
        node.val = val;
    }

    public int sum(String prefix) {
        TrieNode node = root;
        for(char c: prefix.toCharArray()){
            int i = c - 'a';
            if(node.next[i] == null){
                return 0;
            }
            node = node.next[i];
        }
        return dfs(node);
    }

    public int dfs(TrieNode node){
        int res = node.val;
        for(TrieNode nxt: node.next){
            if(nxt != null){
                res += dfs(nxt);
            }
        }
        return res;
    }
}

时间复杂度：O(N) 空间复杂度：O(N)

[shawncvv]

思路

Trie

代码

Python Code

class MapSum:

    def __init__(self):
        self.m = {}
    def insert(self, key, val):
        self.m[key] = val

    def sum(self, prefix):
        count = 0
        for key in self.m:
            if key.startswith(prefix):
                count += self.m[key]
        return count

复杂度

• 时间复杂度：insert: O(1), sum: O(N*S), 其中 N 是目前为止 key 的个数，S 是前缀长度。
• 空间复杂度：O(N)

[chun1hao]

class MapSum {
  map: Map<string, number> = new Map();
  prefixMap: Map<string, number> = new Map();
  insert(key: string, val: number): void {
    let k = "";
    let delta = val - (this.map.get(key) || 0);
    this.map.set(key, val);
    for (let i of key) {
      k += i;
      this.prefixMap.set(k, (this.prefixMap.get(k) || 0) + delta);
    }
  }

  sum(prefix: string): number {
    return this.prefixMap.get(prefix) || 0;
  }
}

[EggEggLiu]

class MapSum {
public:
    unordered_map<string, int> m;
    MapSum() {

    }

    void insert(string key, int val) {
        m[key] = val;
    }

    int sum(string prefix) {
        int ret = 0;
        for (auto pair : m) {
            if (pair.first.find(prefix) == 0)
                ret += pair.second;
        }
        return ret;
    }
};

[skinnyh]

Note

• Can use a traditional dict and implement the sum method by comparing stored keys with prefix.
• Another approach is using Trie tree. Because insert may override node value, for the sum method, we need to do dfs starting from the prefix node for all its children.
• If we want to avoid dfs then can store the sum along the path nodes but will also need another map to store the key value mapping. Once insert overrides the value, we need to update all the path nodes with new_val - old_value.

Solution

class TrieNode:
    def __init__(self):
        self.val = 0
        self.children = {}

class MapSum:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for c in key:
            if c not in node.children:
                node.children[c] = TrieNode()
            node = node.children[c]
        node.val =val

    def sum(self, prefix: str) -> int:
        def dfs(node):
            res = node.val
            for c in node.children:
                res += dfs(node.children[c])
            return res
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        return dfs(node)

Time complexity: insert O(N) N=avg key length, sum worst case O(26^N) traverse all the nodes

Space complexity: O(26^N) All the nodes in trie tree when words share no prefix.

[ZJP1483469269]

class MapSum {
    class Node{
        Node[] children =  new Node[26];
        int val = 0;
    }
    Node root;
    public MapSum() {
        this.root = new Node();
    }

    public void insert(String key, int val) {
        Node node = this.root;
        for(int i = 0 ; i < key.length() ; i++){
            int c = key.charAt(i) - 'a';
            if(node.children[c] == null){
                node.children[c] = new Node();
            }
            node = node.children[c];
        }
        node.val = val;
    }

    public int sum(String prefix) {
        Node node =  this.root;
        for(int i = 0 ;i < prefix.length() ; i++){
            int c = prefix.charAt(i) - 'a';
            if(node.children[c] == null){
                return 0;
            }
            node = node.children[c];
        }
        return dfs(node);        
    }

    public int dfs(Node node){
        if(node == null){
            return 0;
        }
        int ans = 0;
        if(node.val > 0) ans = node.val;
        for(int i = 0 ; i < 26 ; i++){
            ans += dfs(node.children[i]);
        }
        return ans;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

[chakochako]

class MapSum:

    def __init__(self):
        self.trie = dict()

    def insert(self, key: str, val: int) -> None:
        node = self.trie
        for k in key:
            if k not in node:
                node[k] = dict()
            node = node[k]
        node["#"] = val

    def sum(self, prefix: str) -> int:
        node = self.trie
        for k in prefix:
            if k not in node:
                return 0
            node = node[k]
        queue = deque([node])
        ans = 0
        while queue:
            node = queue.popleft()
            for k,v in node.items():
                if k == "#":
                    ans += v
                else:
                    queue.append(v)
        return ans

[RocJeMaintiendrai]

代码

class MapSum {

    private class TrieNode {
        TrieNode[] children = new TrieNode[26];
        int weight = 0;
    }

    TrieNode root = null;
    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.weight = val;
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for(char c : prefix.toCharArray()) {
            if(cur.children[c - 'a'] == null) return 0;
            cur = cur.children[c - 'a'];
        }
        return helper(cur);
    }

    private int helper(TrieNode node) {
        int sum = 0;
        for(char c = 'a'; c <= 'z'; c++) {
            if(node.children[c - 'a'] != null) {
                sum += helper(node.children[c - 'a']);
            }
        }
        return sum + node.weight;
    }
}

复杂度分析

时间复杂度

O(n)

空间复杂度

O(n)

[doveshnnqkl]

class MapSum {
    Map<String, Integer> map;
    public MapSum() {
    map = new HashMap<>();
    }

    public void insert(String key, int val) {
    map.put(key,val);
    }

    public int sum(String prefix) {
     int res = 0;
        for (String s : map.keySet()) {
            if (s.startsWith(prefix)) {
                res += map.get(s);
            }
        }
        return res;

    }
}

[tongxw]

思路

前缀树的扩展

代码

class MapSum {
    int val;
    int sum;
    MapSum[] children;

    public MapSum() {
        this.val = 0;
        this.sum = 0;
        this.children = new MapSum[26];
    }

    public void insert(String key, int val) {
        MapSum node = search(key);
        int preVal = node == null ? 0 : node.val;

        node = this;
        for (int i=0; i<key.length(); i++) {
            int idx = key.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new MapSum();
            }
            node = node.children[idx];
            node.sum += val - preVal;
        }

        node.val = val;
    }

    public int sum(String prefix) {
        MapSum node = search(prefix);
        return node == null ? 0 : node.sum;
    }

    public MapSum search(String str) {
        MapSum node = this;
        for (int i=0; i<str.length(); i++) {
            int idx = str.charAt(i) - 'a';
            node = node.children[idx];
            if (node == null) {
                return null;
            }
        }

        return node;
    }
}

TC: insert O(n), sum O(n), n为单词长度 SC: O(n)

[ghost]

题目

677. Map Sum Pairs

代码

class MapSum:

    def __init__(self):
        self.m = {}

    def insert(self, key: str, val: int) -> None:
        self.m[key] = val

    def sum(self, prefix: str) -> int:
        res = 0

        for key in self.m:
            if key.startswith(prefix):
                res+=self.m[key]

        return res

复杂度

Space: O(N) Time: O(N*len(prefix))

[KennethAlgol]

class MapSum {

    MapSum[] children;

    int val;

    public MapSum() {
        children = new MapSum[26];
    }

    public void insert(String key, int val) {
        if(key.length() == 0) {
            return;
        }
        MapSum cur = this;
        for (int i = 0; i < key.length(); i++) {
            char c = key.charAt(i);
            int index = c - 'a';
            if(cur.children[index] == null) {
                cur.children[index] = new MapSum();
            }
            cur = cur.children[index];
        }
        cur.val = val;
    }

    public int sum(String prefix) {
        //找到当前对应的值
        MapSum cur = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if(cur.children[index] == null) {
                return 0;
            }else {
                cur = cur.children[index];
            }
        }
        return dfs(cur) + cur.val;
    }

    public int dfs(MapSum cur) {
        int res = 0;
        MapSum[] children = cur.children;
        for (int i = 0; i < children.length; i++) {
            if(children[i] != null) {
                res += children[i].val;
                res += dfs(children[i]);
            }
        }
        return res;
    }

}

[jiahui-z]

class MapSum {

    class Node {
        char node;
        int val;
        Node[] children;

        public Node() {
            this.children = new Node[26];
        }

        public Node(char character) {
            this.node = character;
            this.children = new Node[26];
        }
    }

    private Node root;

    public MapSum() {
        this.root = new Node();
    }

    public void insert(String key, int val) {
        Node ptr = root;
        for (int i = 0; i < key.length(); i++) {
            char character = key.charAt(i);
            if (ptr.children[character - 'a'] == null) {
                Node newNode = new Node(character);
                ptr.children[character - 'a'] = newNode;
            }
            ptr = ptr.children[character - 'a'];
        }
        ptr.val = val;
    }

    public int sum(String prefix) {
        Node ptr = root;
        for (int i = 0; i < prefix.length(); i++) {
            char character = prefix.charAt(i);
            if (ptr.children[character - 'a'] == null) {
                return 0;
            }
            ptr = ptr.children[character - 'a'];
        }

        return sum(ptr);
    }

    private int sum(Node node) {
        if (node == null) return 0;

        Node ptr = node;
        int result = node.val;
        for (int i = 0; i < 26; i++) {
            if (ptr.children[i] != null) {
                result += sum(ptr.children[i]);
            }
        }

        return result;
    }
}

/**
 * Your MapSum object will be instantiated and called as such:
 * MapSum obj = new MapSum();
 * obj.insert(key,val);
 * int param_2 = obj.sum(prefix);
 */

[learning-go123]

思路

• 哈希+trie

代码

• 语言支持：Go

Go Code:

type TrieNode struct {
    children [26]*TrieNode
    val      int
}

type MapSum struct {
    root *TrieNode
    cnt  map[string]int
}

func Constructor() MapSum {
    return MapSum{
        root: &TrieNode{},
        cnt:  make(map[string]int),
    }
}

func (this *MapSum) Insert(key string, val int) {
    nVal := val
    if this.cnt[key] > 0 {
        nVal -= this.cnt[key]
    }
    this.cnt[key] = val

    node := this.root
    for _, ch := range key {
        if node.children[ch-'a'] == nil {
            node.children[ch-'a'] = &TrieNode{}
        }
        node = node.children[ch-'a']
        node.val += nVal
    }
}

func (this *MapSum) Sum(prefix string) int {
    node := this.root
    for _, ch := range prefix {
        if node.children[ch-'a'] == nil {
            return 0
        }
        node = node.children[ch-'a']
    }
    return node.val
}

复杂度分析

令 n 为数组长度。

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

[Moin-Jer]

思路

---

Trie

代码

---

class MapSum {

    TrieNode root;

    public MapSum() {

        root = new TrieNode();
    }

    public void insert(String key, int val) {

        TrieNode temp = root;
        for (int i = 0; i < key.length(); i++) {

            if (temp.children[key.charAt(i) - 'a'] == null)
                temp.children[key.charAt(i) - 'a'] = new TrieNode();

            temp = temp.children[key.charAt(i) - 'a'];

        }
        temp.count = val;
    }

    public int sum(String prefix) {

        TrieNode temp = root;

        for (int i = 0; i < prefix.length(); i++) {

            if (temp.children[prefix.charAt(i) - 'a'] == null)
                return 0;

            temp = temp.children[prefix.charAt(i) - 'a'];
        }

        return dfs(temp);
    }

    public int dfs(TrieNode node) {

        int sum = 0;

        for (TrieNode t : node.children)
            if (t != null)
                sum += dfs(t);

        return sum + node.count;
    }

    private class TrieNode {

        int count; 
        TrieNode[] children;

        TrieNode() {

            count = 0;
            children = new TrieNode[26];
        }
    }
}

复杂度分析

---

• 时间复杂度：insert O(n), sum O(m^n)
• 空间复杂度：O(n*m)

[jaysonss]

思路

和Trie标准模板类似，但是需要处理下覆盖的情况，方法就是用哈希表缓存下key及对应的count

class MapSum {

    Node root;

    Map<String,Integer> map;

    public MapSum() {
        root = new Node();
        map = new HashMap();
    }

    public void insert(String key, int val) {
        Node cur = root;
        int delta = val - map.getOrDefault(key,0);//去除被覆盖的count

        for(int i=0;i<key.length();i++){
            int idx = key.charAt(i) - 'a';
            if(cur.children[idx] == null){
                cur.children[idx] = new Node();
            }
            cur.children[idx].prefix+=delta;
            cur = cur.children[idx];
        }
        cur.count += delta;
        map.put(key,cur.count);
    }

    public int sum(String prefix) {
        Node cur = root;

        for(int i=0;i<prefix.length();i++){
            int idx = prefix.charAt(i) - 'a';
            if(cur.children[idx] == null){
                return 0;
            }
            cur = cur.children[idx];
        }
        return cur.prefix;
    }

    private static class Node {
        Node[] children = new Node[26];
        int count = 0;
        int prefix = 0;
    }
}

时间和空间复杂度和标准模板一样

[cassiechris]

思路

hashmap

代码

class MapSum:

    def __init__(self):
        self.m = {}
    def insert(self, key, val):
        self.m[key] = val

    def sum(self, prefix):
        count = 0
        for key in self.m:
            if key.startswith(prefix):
                count += self.m[key]
        return count

[hewenyi666]

题目名称

677. 键值映射

题目链接

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

题目思路

DFS

code for Python3

class MapSum:

    def __init__(self):
        self.trie = dict()

    def insert(self, key: str, val: int) -> None:
        node = self.trie
        for k in key:
            if k not in node:
                node[k] = dict()
            node = node[k]
        node["#"] = val

    def sum(self, prefix: str) -> int:
        node = self.trie
        for k in prefix:
            if k not in node:
                return 0
            node = node[k]
        return self.dfs(node)

    def dfs(self, node):
        ans = 0
        for k in node:
            if k == '#':
                ans += node[k]
            else:
                ans += self.dfs(node[k])
        return ans

复杂度分析

• 时间复杂度: O(N)
• 空间复杂度: O(N)

[shixinlovey1314]

Title:677. Map Sum Pairs

Question Reference LeetCode

Solution

Code

class MapSum {
public:
    MapSum() {
        value = 0;
        total = 0;
        children = vector<MapSum*>(26, NULL);
    }

    void insert(string key, int val) {
        MapSum* cur = find(key);

        MapSum* node = this;
        for (char ch : key) {
            if(node->children[ch - 'a'] == NULL) {
                node->children[ch - 'a'] = new MapSum();
            }

            node = node->children[ch - 'a'];

            if (cur) {
                node->total -= cur->value;
            }

            node->total += val;
        }

        node->value = val;
    }

    MapSum* find(string key) {
        MapSum* node = this;
        for (char ch : key) {
            if(node->children[ch - 'a'] == NULL)
                return NULL;
            node = node->children[ch - 'a'];
        }

        return node;
    }

    int sum(string prefix) {
        MapSum* node = this;
        for (char ch : prefix) {
            if (node->children[ch - 'a'] == NULL) {
                return 0;
            }

            node = node->children[ch - 'a'];
        }

        return node->total;
    }

private:
    int value;
    int total;
    vector<MapSum*> children;

};

Complexity

Time Complexity and Explanation

Space Complexity and Explanation

[Francis-xsc]

思路

Trie+BFS

代码

class MapSum {
private:
    struct Node{
        bool isEnd;
        Node* next[26];
        int value;
        Node(){
            isEnd=false;
            for(int i=0;i<26;i++)
                next[i]=nullptr;
            value=0;
        };
    }*root;
public:
    MapSum() {
        root=new Node();
    }

    void insert(string key, int val) {
        Node* ptr=root;
        for(auto c:key){
            if(ptr->next[c-'a']==nullptr){
                ptr->next[c-'a']=new Node();
            }
            ptr=ptr->next[c-'a'];
        }
        ptr->isEnd=true;
        ptr->value=val;
    }

    int sum(string prefix) {
        Node* ptr=root;
        for(auto c:prefix){
            ptr=ptr->next[c-'a'];
            if(!ptr){
                return 0;
            }
        }
        int res=0;
        queue<Node*> que;
        que.push(ptr);
        while(!que.empty()){
            Node*node=que.front();
            if(node->isEnd)
                res+=node->value;
            for(int i=0;i<26;i++){
                if(node->next[i])
                    que.push(node->next[i]);
            }
            que.pop();
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：insert O(n), sum O(m^n)
• 空间复杂度：O(n*m)

[laurallalala]

代码

class Node():
    def __init__(self, val):
        self.val = val
        self.children = [None]*26

class MapSum(object):

    def __init__(self):
        self.root = Node(0)
        self.d = collections.defaultdict(int)

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: None
        """
        newVal = val
        if key in self.d:
            newVal = val - self.d[key]
        p = self.root
        for c in key:
            idx = ord(c) - ord('a')
            if p.children[idx] == None:
                newNode = Node(newVal)
                p.children[idx] = newNode
            else:
                p.children[idx].val += newVal
            p = p.children[idx]
        self.d[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        p = self.root
        for c in prefix:
            idx = ord(c) - ord('a')
            if not p.children[idx]:
                return 0
            p = p.children[idx]
        return p.val

复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(n)

[muimi]

思路

• 字典树
• 节点存val

• 通过递归计算sum

  代码

  class TrieNode {
  public int val;
  public TrieNode[] children;
  TrieNode() {
  val = 0;
  children = new TrieNode[26];
  }
  }
  class MapSum {
  private TrieNode root;
  
  public MapSum() {
  root = new TrieNode();
  }
  
  public void insert(String key, int val) {
  TrieNode node = root;
  for (char c : key.toCharArray()) {
    if (node.children[c - 'a'] == null) node.children[c - 'a'] = new TrieNode();
    node = node.children[c - 'a'];
  }
  node.val = val;
  }
  
  public int sum(String prefix) {
  TrieNode node = root;
  for (char c : prefix.toCharArray()) {
    if (node.children[c - 'a'] == null) return 0;
    node = node.children[c - 'a'];
  }
  return helper(node);
  }
  private int helper(TrieNode node) {
  int res = node.val;
  for (TrieNode child : node.children) {
    if (child != null) res += helper(child);
  }
  return res;
  }
  }

[AgathaWang]

先马后看

class MapSum:

    def __init__(self):
        self.m = {}
    def insert(self, key, val):
        self.m[key] = val

    def sum(self, prefix):
        count = 0
        for key in self.m:
            if key.startswith(prefix):
                count += self.m[key]
        return count

[zhangyalei1026]

class MapSum(object):
    def __init__(self):
        self.map = {}

    def insert(self, key, val):
        self.map[key] = val

    def sum(self, prefix):
        return sum(val for key, val in self.map.items()
                   if key.startswith(prefix))

[15691894985]

【Day 74】677. 键值映射

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

MapSum 类里两个方法，insert 和sum trie 数据结构

• 每次insert将前缀加入trie，将val存储到trie node中
• sum时，找到对应的trie node ,如果找到在这个Node dfs 将后面方案都加入到count 中，或者在insert时，用一个map记录key，val的值,key已经存在，每次加入值就是读取时候直接读取node的sum

class MapSum:
    def __init__(self):
        self.m = {}

    def insert(self, key: str, val: int) -> None:
        self.m[key] = val

    def sum(self, prefix: str) -> int:
        count = 0
        for key in self.m:
            if key.startswith(prefix):  #startswith 返回以prefix为前缀的节点数
                count += self.m[key]
        return count

复杂度分析：

时间复杂度：插入是O(1),求和是O(N*S) N是key的个数，S是前缀长度

空间复杂度：O(N)N是不重复的key个数

[wenlong201807]

代码块

var MapSum = function () {
  this.root = new Map();
};

/**
 * @param {string} key
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function (key, val) {
  let node = this.root;
  for (const k of key) {
    if (!node.has(k)) node.set(k, new Map());
    node = node.get(k);
  }
  node.set('#', val);
};

/**
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
  let node = this.root;
  for (const k of prefix) {
    if (!node.has(k)) return 0;
    node = node.get(k);
  }
  return this.dfs(node);
};

MapSum.prototype.dfs = function (node) {
  let ans = 0;
  for (const k of node.keys()) {
    if (k == '#') ans += node.get(k);
    else ans += this.dfs(node.get(k));
  }
  return ans;
};

[TimmmYang]

思路

前缀树。

代码

class TrieNode:
    def __init__(self):
        self.dict = {}
        self.isKey = False
        self.value = 0

class MapSum:
    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()

    def insert(self, key: str, val: int) -> None:
        node = self.root
        for ch in key:
            if ch not in node.dict:
                node.dict[ch] = TrieNode()
            node = node.dict[ch]
        node.value = val
        node.isKey = True

    def sum(self, prefix: str) -> int:

        def dfs(node):
            if not node:
                return
            if node.isKey:
                self.res += node.value
            for key in node.dict:
                dfs(node.dict[key])

        node = self.root
        self.res = 0
        for ch in prefix:
            if ch not in node.dict:
                return 0
            # if node.isKey:
            #     self.res += node.value
            node = node.dict[ch]
        dfs(node)
        return self.res

[Daniel-Zheng]

思路

字典树。

代码(C++)

struct TrieNode {
    int val;
    TrieNode * next[26];
    TrieNode() {
        this->val = 0;
        for (int i = 0; i < 26; ++i) {
            this->next[i] = nullptr;
        }
    }
};

class MapSum {
public:
    MapSum() {
        this->root = new TrieNode();
    }

    void insert(string key, int val) {
        int delta = val;
        if (cnt.count(key)) {
            delta -= cnt[key];
        }
        cnt[key] = val;
        TrieNode * node = root;
        for (auto c : key) {
            if (node->next[c - 'a'] == nullptr) {
                node->next[c - 'a'] = new TrieNode();
            }
            node = node->next[c - 'a'];
            node->val += delta;
        }
    }

    int sum(string prefix) {
        TrieNode * node = root;
        for (auto c : prefix) {
            if (node->next[c - 'a'] == nullptr) {
                return 0;
            } else {
                node = node->next[c - 'a'];
            }
        }
        return node->val;
    }
private:
    TrieNode * root;
    unordered_map<string, int> cnt;
};

复杂度分析

• 时间复杂度：O(N)
• 空间复杂度：O(N)