【Day 74 】2024-06-20 - 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

[pandapls]

思路：使用Map存储 暴力遍历累加结果 ··· var MapSum = function() { this.map = new Map() };

/**

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

/**

• @param {string} prefix
• @return {number} */ 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 }; ··· sum: O(n) insert: O(n)

[pandapls]

思路：使用Map存储 暴力遍历累加结果

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

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

/** 
 * @param {string} prefix
 * @return {number}
 */
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
};```
sum: O(n)
insert: O(n)

[Martina001]

思路：前缀树+DFS实现

class MapSum {
        Trie cur;

        public MapSum() {
            cur = new Trie();
        }

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

        public int sum(String prefix) {
            return cur.sum(prefix);
        }

        class Trie {
            Trie[] children;
            int val;

            public Trie() {
                children = new Trie[26];
                val = -1;
            }

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

            public Trie startsWith(String prefix) {
                Trie cur = this;
                for (int i = 0; i < prefix.length(); i++) {
                    char c = prefix.charAt(i);
                    if (cur.children[c - 'a'] == null) {
                        return null;
                    }
                    cur = cur.children[c - 'a'];
                }
                return cur;
            }

            public int sum(String prefix) {
                Trie trie = startsWith(prefix);
                if (trie == null) {
                    return 0;
                }
                return getSum(trie);
            }

            // 递归获取当前节点后续所有key的sum
            private int getSum(Trie trie) {
                if (trie == null) {
                    return 0;
                }
                int res = trie.val == -1 ? 0 : trie.val;
                for (Trie child : trie.children) {
                    if (child != null) {
                        res += child.getSum(child);
                    }
                }
                return res;
            }
        }
    }

[CathyShang]

• insert 使用字典嵌套实现
• sum 先进行前缀判断，若不符合直接return 0，若符合，后续使用DFS遍历尾部求加和

class MapSum:

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

    def insert(self, key: str, val: int) -> None:
        node = self.dic
        for ch in key:
            if ch not in node:
                node[ch] = {}
            node = node[ch]
        node['#'] = val

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

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

时间复杂度: $O(n)$

空间复杂度: $O(n)$

[luzhaofeng]

class MapSum:
    def __init__(self):
        self.d = {}
        self.p = collections.defaultdict(set)

    def insert(self, key: str, val: int) -> None:
        self.d[key] = val
        for i in range(len(key)):
            self.p[key[: i + 1]].add(key)

    def sum(self, prefix: str) -> int:
        return sum(self.d[key] for key in self.p[prefix])

[hillsonziqiu]

代码

/*
 * @lc app=leetcode.cn id=677 lang=javascript
 *
 * [677] 键值映射
 */

// @lc code=start

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

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

/**
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
  let sum = 0;
  for (const key of this.map.keys()) {
    if (key.startsWith(prefix)) {
      sum += this.map.get(key);
    }
  }

  return sum;
};

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

复杂度分析

• 时间复杂度：O(m * n); m是插入map属性的个数，n是前缀的长度；
• 空间复杂度：O(m * n); m是插入map属性的个数，n是key的长度；

[zhiyuanpeng]

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

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

    def insert(self, key: str, val: int) -> None:
        # Calculate the difference between the new value and the old value
        # for the given key, if it exists.
        diff = val - self.map.get(key, 0)
        self.map[key] = val

        # Traverse the Trie from the root to the node that represents
        # the prefix of the key, and update the node value with the new value.
        node = self.root
        node.value += diff
        for char in key:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
            node.value += diff

    def sum(self, prefix: str) -> int:
        # Traverse the Trie from the root to the node that represents
        # the prefix, and return the value of that node.
        node = self.root
        for char in prefix:
            if char not in node.children:
                return 0
            node = node.children[char]
        return node.value

[Dtjk]

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

}