【Day 74 】2022-02-23 - 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

[baddate]

class Trie
{
public:
    unordered_map<char, Trie *> child;
    int val;

    Trie()
    {
        val = 0;
    }

    void insert(string word, int val)
    {
        Trie * root = this;
        for (char c : word)
        {
            if (root->child.find(c) == root->child.end())
                root->child[c] = new Trie();
            root = root->child[c];
        }
        root->val = val;
    }

    int query(string prefix)
    {
        Trie * root = this;
        for (char c : prefix)
        {
            if (root->child.find(c) == root->child.end())
                return 0;
            root = root->child[c];
        }
        return dfs(root);
    }

    int dfs(Trie * root)
    {
        if (root == NULL)
            return 0;
        int res = root->val;
        for (auto [_, ch] : root->child)
            res += dfs(ch);
        return res;
    }

};

class MapSum 
{
public:
    Trie * T;

    /** Initialize your data structure here. */
    MapSum() 
    {
        T = new Trie();
    }

    void insert(string key, int val) 
    {
        T->insert(key, val);
    }

    int sum(string prefix) 
    {
        return T->query(prefix);
    }
};

[hx-code]

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; };

[yetfan]

思路 把昨天的end由true/false 改为数字。 求sum的时候，先找prefix的节点，然后向下遍历求和 这里用None而不是0来表示该节点不存在对应值，用数字表示存在对应值val。因为有可能键值为0，会产生影响。

代码

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

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:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        v = 0
        q = deque([node])
        while q:
            cur = q.popleft()
            if cur.val:
                v += cur.val
            for c in cur.children:
                q.append(cur.children[c])
        return v

[ZJP1483469269]

class MapSum:

    def __init__(self):
        self.children = [None]*26
        self.end = 0
        self.val = None

    def insert(self, key: str, val: int) -> None:
        node = self
        for c in key:
            idx = ord(c) - ord('a')
            if not node.children[idx]:
                node.children[idx] = MapSum()
            node = node.children[idx]
        node.end = 1
        node.val = val
    def dfs(self):
        node = self
        if node.end :
            sum = node.val
        else :
            sum = 0 
        for n in node.children:
            if n:
                sum += n.dfs()
        return sum

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

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

[zwx0641]

class TrieNode { public: TrieNode() : children(26, nullptr), isKey(false), val(0){} vector<TrieNode*> children; bool isKey; int val; };

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

void insert(string key, int val) {
    TrieNode *node = root;
    for (auto ch : key) {
        if (node->children[ch - 'a'] == NULL) {
            node->children[ch - 'a'] = new TrieNode();
        }
        node = node->children[ch - 'a'];
    }
    node->isKey = true;
    node->val = val;
}

int sum(string prefix) {
    TrieNode *node = root;
    for (auto ch : prefix) {
        if (node->children[ch - 'a'] != NULL) {
            node = node->children[ch - 'a'];
        } else {
            return 0;
        }
    }
    return sumVal(node);
}

private: TrieNode root; int sumVal(TrieNode ptr){ int tempSum = 0; if (ptr == NULL){ return 0; } if (ptr->isKey){//如果是key，则累加val tempSum += ptr->val; } //然后统计ptr的所有子节点 for (int i = 0; i < 26; ++i){ if (ptr->children[i] != NULL){ tempSum += sumVal(ptr->children[i]);//递归 } } return tempSum; } };

[xinhaoyi]

class MapSum { // 前缀树根节点： private final TrieNode root = new TrieNode(); // 键-值 map： private final HashMap<String, Integer> map = new HashMap<>();

    // 前缀树节点
    private class TrieNode {
        TrieNode[] paths = new TrieNode[26];
        int sum; 
    }

    public MapSum() {}

    public void insert(String key, int val) {
        int delta = val; // 增加量
        // 如果key已经存在，原来的键值对将被替代成新的键值对，delta为新值减老值
        if (map.containsKey(key)) delta = val - map.get(key);
        map.put(key, val);
        // 前缀树的插入代码 + 更新sum
        TrieNode cur = root;
        cur.sum += delta;
        for (char c : key.toCharArray()) {
            if (cur.paths[c - 'a'] == null) cur.paths[c - 'a'] = new TrieNode();
            cur = cur.paths[c - 'a'];
            cur.sum += delta;
        }
    }

    public int sum(String prefix) {
        // 前缀树的搜索前缀代码：
        TrieNode cur = root;
        for (char c : prefix.toCharArray()) {
            cur = cur.paths[c - 'a'];
            if (cur == null) return 0;
        }
        return cur.sum;
    }
}

[luoyuqinlaura]

思路：

key-value pair, thinking about hashmap<String, Integer>

giving the prefix, check the map, startsWith(), count++, return the count

class MapSum{
  Map<String, Integer> map;

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

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

  public int sum(String prefix) {
    int count = 0;
    //loop through the map key set
    for (String s : map.keySet()) {
      if (s.startsWith(prefix)) {
        count++;
      }
    }
    return count;
  }
}

时间空间：

时间：插入操作O(1)，map的基本操作； 加和O(N*S), N是key的个数，S是放进去的prefix的prefix字符串长度

空间O(N):用了hashmap存储 N is the number of unique key

[Alexno1no2]

class MapSum:

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

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

    def sum(self, prefix: str) -> int:
        return sum(self.d[k] for k in self.d.keys() if k[:len(prefix)]==prefix)

[moirobinzhang]

Code:

public class TrieNode { public TrieNode[] Children = new TrieNode[26]; public int Value; }

public class MapSum { public TrieNode root;

public MapSum() {
    root = new TrieNode();
}

public void Insert(string key, int val) {
    TrieNode node = root;

    foreach(var k in key)
    {
        int index = k - 'a';
        if (node.Children[index] == null)
            node.Children[index] = new TrieNode();

        node = node.Children[index];            
    }

    node.Value = val;
}

public int Sum(string prefix) {
    TrieNode node = root;
    int sum = 0;

    foreach(var p in prefix)
    {
        int index = p - 'a';
        if (node.Children[index] == null)
            return 0;

        node = node.Children[index];

    }

    sum = GetSumDFS(node);

    return sum;       
}

public int GetSumDFS(TrieNode node)
{
    int sum = node.Value;

    foreach(var child in node.Children)
    {
        if (child != null)
            sum += GetSumDFS(child);
    }

    return sum;
}

}

[ZhangNN2018]

class MapSum(object):

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

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: None
        """
        self.dict[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        prefixLen = len(prefix)
        ans = 0
        for key in self.dict:
            if key[0:prefixLen] == prefix:
                ans += self.dict[key]
        return ans

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

[rzhao010]

class MapSum {
    static int N = 2510;
    static int[][] tr = new int[N][26];
    static int[] hash = new int[N];
    static int idx;
    static Map<String, Integer> map = new HashMap<>();

    public MapSum() {
        for (int i = 0; i <= idx; i++) {
            Arrays.fill(tr[i], 0);
        }
        Arrays.fill(hash, 0);
        idx = 0;
        map.clear();
    }

    public void insert(String key, int val) {
        int _val  = val;
        if (map.containsKey(key)) {
            _val -= map.get(key);
        }
        map.put(key, _val);
        for (int i = 0, p = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
            hash[p] += val; 
        }
    }

    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return hash[p];
    }
}

[yan0327]

type Trie struct{
    children [26]*Trie
    Val int
}
type MapSum struct {
    root *Trie
    count map[string]int
}

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

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

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

[1149004121]

677. 键值映射

思路

前缀树。

代码

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

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function(key, val) {
    this.root.insert(key, val);
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function(prefix) {
    let node = this.root;
    for(let char of prefix){
        let index = char.charCodeAt() - "a".charCodeAt();
        if(node.children[index] === 0) return 0;
        node = node.children[index];
    };
    return node.sum;
};

class TrieNode {
    constructor(){
        this.children = new Array(26).fill(0);
        this.sum = 0;
        this.val = 0;
        this.end = false;
    };
    insert(word, num){
        let node = this;
        let oldVal = this.search(word);
        for(let char of word){
            let index = char.charCodeAt() - "a".charCodeAt();
            if(node.children[index] === 0){
                node.children[index] = new TrieNode();
            };
            node = node.children[index];
            node.sum = node.sum - oldVal + num;
        }; 
        node.end = true;
        node.val = num;     
    };
    search(word){
        let node = this;
        for(let char of word){
            let index = char.charCodeAt() - "a".charCodeAt();
            if(node.children[index] === 0) return 0;
            node = node.children[index];
        };
        return node.end ? node.val : 0;
    }
}

复杂度分析

• 时间复杂度：O(L) ，L是word长度；。
• 空间复杂度：O(N*L)。

[xuhzyy]

class TreeNode:
    def __init__(self):
        self.pre = 0
        self.cnt = 0
        self.children = {}

class MapSum:

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

    def insert(self, key: str, val: int) -> None:
        # find key
        existed, node = True, self.root
        for ch in key:
            if ch not in node.children:
                existed = False
                break 
            node = node.children[ch]
        cnt = node.cnt if existed else 0

        # insert key
        node = self.root
        for ch in key:
            if ch not in node.children:
                node.children[ch] = TreeNode()
            node = node.children[ch]
            node.pre += val - cnt
        node.cnt += val - cnt

    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.pre

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

[mannnn6]

class MapSum {
    HashMap<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 ans = 0;
        for (String key: map.keySet()) {
            if (key.startsWith(prefix)) {
                ans += map.get(key);
            }
        }
        return ans;
    }
}

[tongxw]

思路

前缀树实现累加

class MapSum {
    Map<Character, MapSum> children;
    int sum;
    int val;
    public MapSum() {
        children = new HashMap<>();
        sum = 0;
        val = 0;
    }

    public void insert(String key, int val) {
        MapSum cur = search(key);
        int prev = cur == null ? 0 : cur.val;
        int diff = val - prev;

        // update sum
        cur = this;
        for (char c : key.toCharArray()) {
            cur = cur.children.computeIfAbsent(c, k -> new MapSum());
            cur.sum += diff;
        }

        // update value
        cur.val = val;
    }

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

    public MapSum search(String key) {
        MapSum cur = this;
        for (char c : key.toCharArray()) {
            cur = cur.children.getOrDefault(c, null);
            if (cur == null) {
                break;
            }
        }

        return cur;
    }
}

TC: insert: O(n), sum O(n) SC: linear size to how many times input() gets called.

[zjsuper]

class MapSum:

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

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

    def sum(self, prefix: str) -> int:
        ans = 0
        for k,v in self.map.items():
            if len(prefix)<=len(k):
                if prefix == k[0:len(prefix)]:
                    ans+=v
        return ans

[callmeerika]

思路

前缀树

代码

var MapSum = function () {
  this.children = {};
  this.count = 0;
};

MapSum.prototype.insert = function (key, val) {
  let node = this.children;
  for (let index = 0; index < key.length; index++) {
    let i = key[index];
    if (!node[i]) node[i] = new MapSum();
    if (index === key.length - 1) {
      node[i].count = val;
    }
    node = node[i].children;
  }
};

MapSum.prototype.sum = function (prefix) {
  let node = this.children;
  const dfs = ele => {
    if (!Object.keys(ele.children).length) return 0;
    let count = 0;
    for (let key in ele.children) {
      count += ele.children[key].count + dfs(ele.children[key]);
    }
    return count;
  };
  for (let index = 0; index < prefix.length; index++) {
    let i = prefix[index];
    if (!node[i]) return 0;
    if (index === prefix.length - 1) {
      node = node[i];
    } else {
      node = node[i].children;
    }
  }
  return dfs(node) + node.count || 0;
};

复杂度

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

[haixiaolu]

思路

HashMap

# HashMap
class MapSum:

    def __init__(self):
        self.map = {}
        self.score = collections.Counter()

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)
        self.map[key] = val
        for i in range(len(key) + 1):
            prefix = key[:i]
            self.score[prefix] += delta

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

复杂分析

• Time: insert O(n^2), n是插入的字符串key的长度， 我们需要把字符串的所有前缀都在哈希表中插入一次， sum操作O(1)
• Space: O(mn)

[Bochengwan]

思路

Trie

代码

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

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.root = TrieNode()
        self.map = collections.defaultdict(int)

    def insert(self, key: str, val: int) -> None:
        delta = val-self.map[key]
        self.map[key] = val
        curr = self.root
        for e in key:
            if e not in curr.children:
                curr.children[e] = TrieNode()
            curr = curr.children[e]
            curr.val +=delta

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

复杂度分析

• 时间复杂度：insert O(N)，其中 N 为键的个数, sum O(N)。
• 空间复杂度：O(1)

[CoreJa]

思路

熟悉前缀树写法就比较容易AC。

• 前缀树+无限嵌套：使用了zhy秘技之无限套娃字典defaultdict(x:=lambda: defaultdict(x))。不过因为默认为字典类型，反而有很多别的地方需要额外判断。具体细节看下面。复杂度$O(n)$
• 前缀树：普通实现，题目的sum要求的前缀树的任意节点的前缀和，所以每次插入时需要给每个节点累加val，同时题目要求如果插入相同字符，则要替换掉val，所以插入前需要先搜索其是否存在，如果存在则需要先把它对应val减掉。复杂度$O(n)$

代码

# 前缀树+无限嵌套：使用了zhy秘技之无限套娃字典`defaultdict(x:=lambda: defaultdict(x))`。
# 不过因为默认为字典类型，反而有很多别的地方需要额外判断。具体细节看下面。复杂度$O(n)$
class MapSum1:
    def __init__(self):
        self.root = defaultdict(x := lambda: defaultdict(x))

    def search(self, key: str) -> defaultdict:
        node = self.root
        for ch in key:
            node = node[ch]
        return node

    def insert(self, key: str, val: int) -> None:
        node = self.search(key)
        pre_val = node['!'] if '!' in node else 0
        node = self.root
        for ch in key:
            node = node[ch]
            node['#'] = node['#'] + val - pre_val if '#' in node else val - pre_val
        node['!'] = val

    def sum(self, prefix: str) -> int:
        node = self.search(prefix)
        return node['#'] if '#' in node else 0

# 前缀树：普通实现，题目的sum要求的前缀树的任意节点的前缀和，所以每次插入时需要给每个节点累加`val`，同时题目要求如
# 果插入相同字符，则要替换掉`val`，所以插入前需要先搜索其是否存在，如果存在则需要先把它对应`val`减掉。复杂度$O(n)$
class MapSum:
    def __init__(self):
        self.root = defaultdict(int)

    def search(self, key: str) -> int:
        node = self.root
        for ch in key:
            if ch not in node:
                node[ch] = defaultdict(int)
            node = node[ch]
        return node

    def insert(self, key: str, val: int) -> None:
        node = self.search(key)
        pre_val = node['!']
        node = self.root
        for ch in key:
            node = node[ch]
            node['#'] += +val - pre_val
        node['!'] = val

    def sum(self, prefix: str) -> int:
        node = self.search(prefix)
        return node['#']

[zhiyuanpeng]

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

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:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        v = 0
        q = deque([node])
        while q:
            cur = q.popleft()
            if cur.val:
                v += cur.val
            for c in cur.children:
                q.append(cur.children[c])
        return v

[LannyX]

思路

HashMap

代码

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 count = 0;
        for(String key : map.keySet()){
            if(key.startsWith(prefix)){
                count += map.get(key);
            }
        }
        return count;
    }
}

复杂度分析

• 时间复杂度：O(n)

[Tesla-1i]

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

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:
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        v = 0
        q = deque([node])
        while q:
            cur = q.popleft()
            if cur.val:
                v += cur.val
            for c in cur.children:
                q.append(cur.children[c])
        return v

[honeymeng-hub]

class MapSum{ Map<String, Integer> map;

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

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

public int sum(String prefix) { int count = 0; //loop through the map key set for (String s : map.keySet()) { if (s.startsWith(prefix)) { count++; } } return count; } }

[falconruo]

思路: 字典树 + 哈希

复杂度分析:

• 时间复杂度: O(N * K)，N为前缀长度, K为哈希表key的个数
• 空间复杂度: O(K), K为哈希表key的个数

代码(C++):

struct TrieNode {
    TrieNode *child[26];
    bool is_string = false;
};

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

    void insert(string key, int val) {
        TrieNode *p = root;

        for (char c : key) {
            int i = c - 'a';
            if (!p->child[i]) p->child[i] = new TrieNode();
            p = p->child[i];
        }
        p->is_string = true;
        mp[key] = val;
    }

    int sum(string prefix) {
        int res = 0;

        for (auto it = mp.begin(); it != mp.end(); it++) {
            int pos = it->first.find(prefix);
            if (pos == 0 && pos != string::npos)
                res += it->second;
        }

        return res;
    }
private:
    TrieNode *root;
    unordered_map<string, int> mp;
};

[JudyZhou95]

class TrieNode(object):
    __slots__ = "children", "score"
    def __init__(self):
        self.children = {}
        self.score = 0

class MapSum:

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

    def insert(self, key: str, val: int) -> None:
        delta = val - self.map.get(key, 0)
        self.map[key] = val
        cur = self.root
        cur.score += delta

        for char in key:
            cur = cur.children.setdefaul(char, TrieNode())
            cur.score += delta

    def sum(self, prefix: str) -> int:
        cur = self.root

        for char in prefix:
            if char not in cur.children:
                return 0

            cur = cur.children[char]

        return cur.score

"""
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):
                count += self.m[key]
        return count

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

[luhnn120]

思路

字典树

代码

class TrieNode {
    constructor() {
        this.val = 0;
        this.next = new Array(26).fill(0);
    }
}

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

};

MapSum.prototype.insert = function(key, val) {
    const delta = val - (this.map.get(key) || 0);
    this.map.set(key, val);
    let node = this.root;
    for (const c of key) {
        if (node.next[c.charCodeAt() - 'a'.charCodeAt()] === 0) {
            node.next[c.charCodeAt() - 'a'.charCodeAt()] = new TrieNode();
        }
        node = node.next[c.charCodeAt() - 'a'.charCodeAt()];
        node.val += delta;
    }
};

MapSum.prototype.sum = function(prefix) {
    let node = this.root;
    for (const c of prefix) {
        if (node.next[c.charCodeAt() - 'a'.charCodeAt()] === 0) {
            return 0;
        }
        node = node.next[c.charCodeAt() - 'a'.charCodeAt()];
    }
    return node.val;
};

复杂度

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

[Toms-BigData]

type MapSum struct {
    strlist map[string]int
    hashmap map[string]int
}

func Constructor() MapSum {
    return struct {
        strlist map[string]int
        hashmap map[string]int
    }{strlist: map[string]int{}, hashmap: map[string]int{}}
}

func (this *MapSum) Insert(key string, val int)  {
    if _,ok:=this.strlist[key];ok{
        for i := 1; i <= len(key); i++ {
            this.hashmap[key[0:i]] = this.hashmap[key[0:i]] + val - this.strlist[key]
        }
        this.strlist[key] = val
    }else {
        this.strlist[key] = val
        for i := 1; i <= len(key); i++ {
            if _,ok:=this.hashmap[key[0:i]];ok{
                this.hashmap[key[0:i]] += val
            }else {
                this.hashmap[key[0:i]] = val
            }
        }
    }

}

func (this *MapSum) Sum(prefix string) int {
    return this.hashmap[prefix]
}

[charlestang]

思路

解法一：哈希

用哈希存储 key-value，求 sum 时候遍历所有 key

class MapSum:

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

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

    def sum(self, prefix: str) -> int:
        s = 0
        for k,v in self.pairs.items():
            if k.startswith(prefix):
                s += v
        return s

时间复杂度： insert- O(1), sum- O(n) 空间复杂度： O(n)

解法二：字典树 + 前缀和

在 key 的每个前缀上，都把 value 累加上去，形成前缀和。

使用字典树来记录前缀和。

class MapSum:

    def __init__(self):
        self.values = defaultdict(int)
        self.d = {}

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

        d = self.d
        for c in key:
            if c not in d:
                d[c] = {}
            d = d[c]
            if 'val' not in d:
                d['val'] = delta
            else:
                d['val'] += delta

    def sum(self, prefix: str) -> int:
        d = self.d
        for c in prefix:
            if c not in d:
                return 0
            d = d[c]
        return d['val']

时间复杂度： insert - O(len(key)), sum - O(len(prefix))

[Rex-Zh]

思路

• 学习了前缀树Trie
• 在以节点结束统计赋值value

• 使用dfs遍历前缀下的子树累加实现sum

  代码

  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];
      }
  }
  }

  复杂度

• 时间：插入操作是线性复杂度，sum 操作最坏情况是O(m^n)（可以理解成从根结点遍历了所有节点）
• 空间：O(t)，其中 t 为 words 的总字符乘以字符集大小（如果是小写英文字母，那么字符集大小就是 26）

[Myleswork]

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

[hdyhdy]

type MapSum struct {
    num map[string]int
    name []string
}

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

func (this *MapSum) Insert(key string, val int)  {
    if this.num[key] == 0 {
        this.name = append(this.name,key)
    }
        this.num[key] = val
}

func (this *MapSum) Sum(prefix string) int {
    ans := 0
    lenght := len(prefix)
    for i := 0 ; i < len(this.name); i ++ {
        num := 0
        if lenght <= len(this.name[i]){
        for j := 0; j < lenght;j ++ {
            if prefix[j] == this.name[i][j]{
                num ++ 
            }
        }
        if num == lenght {
            ans += this.num[this.name[i]]
        }   
    }
}
    return ans 
}

/**
 * Your MapSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Insert(key,val);
 * param_2 := obj.Sum(prefix);
 */

[Aobasyp]

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 count = 0;

    for (String key: map.keySet())
        if(key.startsWith(prefix))
            count += map.get(key);

    return count;
}

}

空间复杂度：O(N) 时间复杂度：插入是O(1)，求和操作是O(N * S)

[biscuit279]

思路

朴实无华哈希表

class MapSum(object):

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

    def insert(self, key, val):
        """
        :type key: str
        :type val: int
        :rtype: None
        """
        self.hash_table[key] = val

    def sum(self, prefix):
        """
        :type prefix: str
        :rtype: int
        """
        ans = 0
        for k,v in self.hash_table.items():
            if str(k).startswith(prefix):
                ans += v
        return ans

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

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

[CodingProgrammer]

思路

前缀树

代码

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

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

    TrieNode root;
    Map<String, Integer> map;

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

    public void insert(String key, int val) {
        int diff = val - this.map.getOrDefault(key, 0);
        this.map.put(key, val);
        TrieNode curr = this.root;
        for (char c : key.toCharArray()) {
            int idx = c - 'a';
            if (curr.children[idx] == null) {
                curr.children[idx] = new TrieNode();
            }
            curr = curr.children[idx];
            curr.val += diff;
        }
    }

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

/**
 * 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 O(N), sum O(N)
• 空间复杂度：O(CNM)

[guangsizhongbin]

type MapSum map[string]int

func Constructor() MapSum { return MapSum{} }

func (m MapSum) Insert(key string, val int) { m[key] = val }

func (m MapSum) Sum(prefix string) int { sum := 0 for s, v := range m { if strings.HasPrefix(s, prefix){ sum += v } } return sum

}

/**

• Your MapSum object will be instantiated and called as such:
• obj := Constructor();
• obj.Insert(key,val);
• param_2 := obj.Sum(prefix); */

[spacker-343]

思路

前缀树

代码

class MapSum {

    class TrieNode {
        int val;
        TrieNode[] node = new TrieNode[26];
    }

    TrieNode root = new TrieNode();
    Map<String, Integer> map;

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

    public void insert(String key, int val) {
        int temp = val;
        val -= map.getOrDefault(key, 0);
        map.put(key, temp);
        char[] c = key.toCharArray();
        int len = c.length;
        TrieNode cur = root;
        for (int i = 0; i < len; i++) {
            if (cur.node[c[i] - 'a'] == null) {
                cur.node[c[i] - 'a'] = new TrieNode();
            }
            cur = cur.node[c[i] - 'a'];
            cur.val += val;
        }
    }

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

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

[Jay214]

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

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function(key, val) {
    this.map[key] = val
};

/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function(prefix) {
    return Object.keys(this.map).reduce((pre, cur) => {
        return cur.indexOf(prefix) === 0 ? pre + this.map[cur] : pre
    }, 0)
};

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

[Richard-LYF]

class TrieNode: def init(self): self.val = 0 self.next = [None for _ in range(26)]

class MapSum: def init(self): self.root = TrieNode() self.map = {}

def insert(self, key: str, val: int) -> None:
    delta = val
    if key in self.map:
        delta -= self.map[key]
    self.map[key] = val
    node = self.root
    for c in key:
        if node.next[ord(c) - ord('a')] is None:
            node.next[ord(c) - ord('a')] = TrieNode()
        node = node.next[ord(c) - ord('a')]
        node.val += delta

def sum(self, prefix: str) -> int:
    node = self.root
    for c in prefix:
        if node.next[ord(c) - ord('a')] is None:
            return 0            
        node = node.next[ord(c) - ord('a')]
    return node.val

[ZacheryCao]

Idea

Trie + HashTable + DFS

Code

class MapSum:

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

    def insert(self, key: str, val: int) -> None:
        cur = self.root
        for i in key:
            cur = cur.setdefault(i, {})
        cur["#"] = val

    def sum(self, prefix: str) -> int:
        ans = 0
        cur = self.root
        for i in prefix:
            if i not in cur:
                return 0
            cur = cur[i]
        def dfs(node):
            nonlocal ans
            for i in node:
                if i == "#":
                    ans += node[i]
                    continue
                dfs(node[i])
        dfs(cur)
        return ans

Complexity:

Insert: Time: O(N): N: length of the key Space: O(N)

Sum: Time: O(M): M: the amount of the nodes that prefix has Space: O(K): K: the longest path of the subtree with prefix as first several nodes

[googidaddy]

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; };

[fornobugworld]

class TrieNode: def init(self): self.val = 0 self.next = [None for _ in range(26)]

class MapSum: def init(self): self.root = TrieNode() self.map = {}

def insert(self, key: str, val: int) -> None:
    delta = val
    if key in self.map:
        delta -= self.map[key]
    self.map[key] = val
    node = self.root
    for c in key:
        if node.next[ord(c) - ord('a')] is None:
            node.next[ord(c) - ord('a')] = TrieNode()
        node = node.next[ord(c) - ord('a')]
        node.val += delta

def sum(self, prefix: str) -> int:
    node = self.root
    for c in prefix:
        if node.next[ord(c) - ord('a')] is None:
            return 0            
        node = node.next[ord(c) - ord('a')]
    return node.val

[Hacker90]

class TrieNode: def init(self): self.val = 0 self.next = [None for _ in range(26)]

class MapSum: def init(self): self.root = TrieNode() self.map = {}

def insert(self, key: str, val: int) -> None: delta = val if key in self.map: delta -= self.map[key] self.map[key] = val node = self.root for c in key: if node.next[ord(c) - ord('a')] is None: node.next[ord(c) - ord('a')] = TrieNode() node = node.next[ord(c) - ord('a')] node.val += delta

def sum(self, prefix: str) -> int: node = self.root for c in prefix: if node.next[ord(c) - ord('a')] is None: return 0
node = node.next[ord(c) - ord('a')] return node.val

[ChenJingjing85]

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

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

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

    def dfs(self, node, count):
        count += node.val
        for c in node.children:
            childNode = node.children[c]
            print('before dfs', c, childNode.val, count)
            count = self.dfs(childNode, count)
            print('after dfs', c, childNode.val, count)
        return count

    def sum(self, prefix: str) -> int:
        res = 0
        node = self.root
        for c in prefix:
            if c not in node.children:
                return 0
            node = node.children[c]
        #从node开始dfs累加以node为根的子树的所有叶子节点的值即可
        return self.dfs(node,0)

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

[for123s]

struct triNode
{
    int key_val;
    vector<triNode*> children;
    triNode()
    {
        children.assign(26, NULL);
        key_val = 0;
    }
};
class MapSum {
public:
    triNode* root;
    unordered_map<string,int> mp;
    MapSum() {
        root = new triNode();
        mp.clear();
    }

    void insert(string key, int val) {
        if(mp.count(key)==1)
            val -= mp[key];
        mp[key] += val;
        triNode* temp = root;
        for(int i=0;i<key.size();i++)
        {
            int idx = key[i] - 'a';
            if(!temp->children[idx])
                temp->children[idx] = new triNode();
            temp->children[idx]->key_val += val;
            temp = temp->children[idx];
        }
    }

    int sum(string prefix) {
        triNode* temp = root;
        for(int i=0;i<prefix.size();i++)
        {
            int idx = prefix[i] - 'a';
            if(!temp->children[idx])
                return 0;
            temp = temp->children[idx];
        }
        return temp->key_val;
    }
};

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

[zzzpppy]

class MapSum {
    int[][] tr = new int[2510][26];
    int[] hash = new int[2510];
    int idx;
    public void insert(String key, int val) {
        int p = 0;
        for (int i = 0; i < key.length(); i++) {
            int u = key.charAt(i) - 'a';
            if (tr[p][u] == 0) tr[p][u] = ++idx;
            p = tr[p][u];
        }
        hash[p] = val;
    }
    public int sum(String prefix) {
        int p = 0;
        for (int i = 0; i < prefix.length(); i++) {
            int u = prefix.charAt(i) - 'a';
            if (tr[p][u] == 0) return 0;
            p = tr[p][u];
        }
        return dfs(p);
    }
    int dfs(int p) {
        int ans = hash[p];
        for (int u = 0; u < 26; u++) {
            if (tr[p][u] != 0) ans += dfs(tr[p][u]);
        }
        return ans;
    }
}

[taojin1992]

/*
# Bruteforce:

Store each key - val pair into hashmap, for each prefix, sum up the value for the keys of the same prefix

n = unumber of keys in the map

## Time complexity:
for each insert: O(1)
for each sum operation: O(n * prefex_length)

## Space complexity:
O(n)

# Optimization:
Trie

Node contains:
TrieNode[] children, size = 26
isWord: boolean, is it a complete word given?
val: as given in the pair
--> isWord == true, val = given val for the word
--> isWord = false, val = 0 for that TrieNode

*/

class MapSum {
    private class TrieNode {
        TrieNode[] children;
        int val; // the value of current word inserted
        boolean isWord;
        int sum; // the sum of words' val sharing the given prefix

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

    /** Initialize your data structure here. */
    TrieNode root;

    public MapSum() {
        root = new TrieNode();
    }

    public void insert(String key, int val) {
        TrieNode cur = root;
        int oldVal = searchKey(key);
        for (int i = 0; i < key.length(); i++) {
            // no such child path, then create this path
            if (cur.children[key.charAt(i) - 'a'] == null) {
                cur.children[key.charAt(i) - 'a'] = new TrieNode();
            }
            // progress the cur pointer
            cur = cur.children[key.charAt(i) - 'a'];
            // in case we have inserted the same key, update
            cur.sum = cur.sum - oldVal + val;
        }
        // finish the inserting
        cur.val = val;
        cur.isWord = true;
    }

    public int searchKey(String key) {
        TrieNode cur = root;
        for (int i = 0; i < key.length(); i++) {
            // no such prefix
            if (cur.children[key.charAt(i) - 'a'] == null) {
                return 0;
            }
            // progress the cur pointer
            cur = cur.children[key.charAt(i) - 'a'];
        }
        return cur.isWord ? cur.val : 0; // if not word, then 0, no need to subtract anything
    }

    public int sum(String prefix) {
        TrieNode cur = root;
        for (int i = 0; i < prefix.length(); i++) {
            // no such prefix
            if (cur.children[prefix.charAt(i) - 'a'] == null) {
                return 0;
            }
            // progress the cur pointer
            cur = cur.children[prefix.charAt(i) - 'a'];
        }
        return cur.sum;
    }

    /*
    Map<String, Integer> strValMap;

    public MapSum() {
        strValMap = new HashMap<>();
    }

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

    public int sum(String prefix) {
        int sum = 0;
        for (String str : strValMap.keySet()) {
            if (str.startsWith(prefix)) {
                sum += strValMap.get(str);
            }
        }
        return sum;
    }
    */
}

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

[zhangzz2015]

思路

• 采用Trie 数据结构，同时用map记录当前val，这样通过每次更新delta实现。从top 到 down更新。时间复杂度为O(n)，空间复杂度为O(n*m)

` struct Node{ vector<Node*> child; int val;

Node(int _val)
{
    child.resize(26, NULL); 
    val = _val; 
}        

}; class MapSum { public: Node* root; MapSum() {
root = new Node(0);
} unordered_map<string, int> record;
void insert(string key, int val) {

    int prev =0; 
    if(record.count(key))
    {
        prev = record[key]; 
    }

    record[key] = val; 

    int delta = val - prev; 
    Node* current = root; 
    for(auto& it: key)
    {
        int index = it - 'a'; 
        if(current->child[index]==NULL)
        {
           current->child[index] = new Node(delta);  
        }
        else 
            current->child[index]->val += delta; 
        current = current->child[index]; 
    }                
}

int sum(string prefix) {
    Node* current = root; 
    for(auto& it : prefix)
    {
        int index = it - 'a'; 
        if(current->child[index]==NULL)
            return 0; 
        current = current->child[index]; 
    }
    return current->val; 
}

};

/**

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

[declan92]

思路

1.使用哈希表保存key,value;将所有的key保存在前缀树中;
2.前缀树定义precount保存以该结点结束的所有前缀的value总和;
3.插入key,value时,每个字符结点preCount+=value,注意如果key已经存在,则preCount += value - preValue;

java

class MapSum {
    Map<String,Integer> map;
    //int count;
    int preCount;
    MapSum[] chirden;

    public MapSum() {
        map = new HashMap<>();
        //count = 0;
        preCount = 0;
        chirden = new MapSum[26];
    }

    public void insert(String key, int val) {
        MapSum node = this;
        boolean flag = map.containsKey(key);
        for (int i = 0; i < key.length(); i++) {
            int index = key.charAt(i) - 'a';
            if(node.chirden[index]==null){
                node.chirden[index] = new MapSum();
            }
            node = node.chirden[index];
            if(flag){
                node.preCount += val - map.get(key);
            }else{
                node.preCount += val;
            }
        }
        map.put(key, val);
        //node.count = val;
    }

    public int sum(String prefix) {
        MapSum node = this;
        for (int i = 0; i < prefix.length(); i++) {
            int index = prefix.charAt(i) - 'a';
            if(node.chirden[index]==null){
                return 0;
            }
            node = node.chirden[index];
        }
        return node.preCount;
    }
}

时间:构造方法$O(1)$;插入,查询$O(len(key))$;
空间:$O(m*n)$,m为字符集长度(本题26),n为所有插入key的字符总数;