【Day 74 】2023-04-28 - 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

[Fuku-L]

代码

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

    public void insert(String key, int val) {
        int detal = val - map.getOrDefault(key, 0);
        map.put(key, val);
        for(int i = 1; i<=key.length(); i++){
            String cur = key.substring(0,i);
            prefixmap.put(cur, prefixmap.getOrDefault(cur, 0) +detal);
        }
    }

    public int sum(String prefix) {
        return prefixmap.getOrDefault(prefix, 0);
    }
}

复杂度分析

• 时间复杂度：insert: O(N^2)，sum: O(1)其中 N 为数组长度。
• 空间复杂度：O(MN)

[NorthSeacoder]

/**
 * Initialize your data structure here.
 */
var MapSum = function () {
    this.node = {};
    this.map = new Map()
};

/** 
 * @param {string} key 
 * @param {number} val
 * @return {void}
 */
MapSum.prototype.insert = function (key, val) {
    let node = this.node;
    const map = this.map;
    if (map.has(key)) {
        const res = map.get(key)
        const diff = val - res
        for (let char of key) {
            node = node[char]
            node.val += diff;
        }
    } else {
        for (let char of key) {
            if (!node[char]) node[char] = { val: 0 };
            node = node[char];
            node.val += val
        }
        node.isWord = true;
    }
    map.set(key, val)

};
/** 
 * @param {string} prefix
 * @return {number}
 */
MapSum.prototype.sum = function (prefix) {
    let node = this.node;
    for (let char of prefix) {
        if (!node[char]) return null;
        node = node[char]
    }
    return node.val
};

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

[Diana21170648]

思路

前缀树

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

**复杂度分析**
- 时间复杂度：nsert/sum:T=O(n),n为不重复的key的个数

- 空间复杂度：insert:S=O(1),sum:S=O(n*s)，n为目前为止前缀key的个数，s为前缀的长度

[huizsh]

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

[LIMBO42]

class MapSum {
public:
    /** Initialize your data structure here. */
    struct trieNode{
        char ch;
        unordered_map<char, trieNode*> next;
        bool end = false;
        int val = 0;
        trieNode() {

        }
        trieNode(char c) {
            ch = c;
        }
    };
    trieNode* root = new trieNode;
    unordered_map<string, int> key2val;
    MapSum() {

    }

    void insert(string key, int val) {
        int diff = 0;
        // if(key2val.count(key)) {
        //     diff = key2val[key];
        // }
        key2val[key] = val;
        int add = val - diff;
        trieNode* node = root;
        for(char ch : key) {
            if(!node->next.count(ch)) {
                trieNode* tmp = new trieNode(ch);
                node->next[ch] = tmp;
            }
            node = node->next[ch];
            // node->val += add;
        }
        node->end = true;
        // node->val += add;
        node->val = val;
    }
    void dfs(trieNode* root, int &sum) {
        if(root == nullptr) return;
        sum += root->val;
        for(auto it : root->next) {
            dfs(it.second, sum);
        }
    }
    int sum(string prefix) {
        int ans = 0;
        trieNode* node = root;
        for(char ch : prefix) {
            if(!node->next.count(ch)) return ans;
            node = node->next[ch];
        }
        // return node->val;
        // int ans = 0;
        dfs(node, ans);
        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);
 */

[Abby-xu]

class MapSum:

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

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

    def sum(self, prefix: str) -> int:
        out, n = 0, len(prefix)
        for item in self.dic:
            if item[:n] == prefix:
                out += self.dic[item]
        return out

[FireHaoSky]

思路：前缀树，dfs

代码：python

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

复杂度分析：

"""
时间复杂度：O(N)
空间复杂度：O(clen(map)len(key))
"""

[61hhh]

思路

insert可以改造trie构造中的插入方法；sum是prefix最后一个字符的val

代码

class MapSum {
    class Trie {
        int val = 0;
        Trie[] next = new Trie[26];
    }

    Trie root;
    Map<String, Integer> map;

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

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        Trie node = root;
        for (char c : key.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                node.next[c - 'a'] = new Trie();
            }
            node = node.next[c - 'a'];
            node.val += delta;
        }
    }

    // 只需要返回prefix最后一个字符的val即可
    public int sum(String prefix) {
        Trie node = root;
        for (char c : prefix.toCharArray()) {
            if (node.next[c - 'a'] == null) {
                return 0;
            }
            node = node.next[c - 'a'];
        }
        return node.val;
    }
}

复杂度分析

• 时间复杂度：创建O(N)
• 空间复杂度：O(key最大长度 * map长度)

[snmyj]

class MapSum {
public:
    map<string,int> mapsum;
    MapSum() {

    }

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

    int sum(string prefix) {
        int sum=0;
     for(auto [x,val]:mapsum){
         if(x.substr(0,prefix.length())==prefix){
            sum+=val;
         }
     }    
        return sum; 
     }   

};

[bookyue]

TC: O(n)
SC: O(n)

class MapSum {
    private final MapSum[] children;
    private final Map<String, Integer> map;
    private int val;

    public MapSum() {
        children = new MapSum[26];
        map = new HashMap<>();
        val = 0;
    }

    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        MapSum node = this;
        for (char c : key.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null)
                node.children[idx] = new MapSum();

            node = node.children[idx];
            node.val += delta;
        }
    }

    public int sum(String prefix) {
        MapSum node = this;
        for (char c : prefix.toCharArray()) {
            int idx = c - 'a';

            if (node.children[idx] == null) return 0;

            node = node.children[idx];
        }

        return node.val;
    }
}

[harperz24]

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

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

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

        cur = self.root
        for ch in key:
            if ch not in cur.children:
                cur.children[ch] = TrieNode()
            cur = cur.children[ch]
            cur.value += delta 

        # time: O(len(key))
        # space: O(number of keys * max length of keys)      

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

        # time: O(len(prefix))
        # space: O(len(prefix))

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

[kofzhang]

思路

Trie树应用

复杂度

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

代码

class TreeNode:
    def __init__(self):
        self.nodes = defaultdict(TreeNode)
        self.end = False
        self.value = 0
        self.passvalue=0

class MapSum:

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

    def getvalue(self,key:str) -> int:
        index = 0
        node = self.data
        while index<len(key):
            node = node.nodes[key[index]]
            index += 1
        if node.end:
            return node.value
        else:
            return 0

    def insert(self, key: str, val: int) -> None:  
        oldvalue = self.getvalue(key)
        index = 0
        node = self.data
        while index<len(key):
            node = node.nodes[key[index]]
            node.passvalue += val-oldvalue
            index += 1
        node.end = True
        node.value = val

    def sum(self, prefix: str) -> int:
        index = 0
        node = self.data
        while index<len(prefix):
            node = node.nodes[prefix[index]]     
            index += 1
        return node.passvalue      

[wangqianqian202301]

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

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

    def insert(self, key: str, val: int) -> None:
        delta = val - self.m.get(key,0)
        self.m[key] = val
        node = self.t
        for char in key:
            node = node.children[char]
            node.value += delta

    def sum(self, prefix: str) -> int:
        node = self.t
        for char in prefix:
            node = node.children.get(char)
            if not node:
                return 0
        return node.value

[RestlessBreeze]

code

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

[JasonQiu]

class Node:
    def __init__(self, count=0):
        self.children = collections.defaultdict(Node)
        self.count = count

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

    def insert(self, key: str, val: int) -> None:
        delta = val - self.keys.get(key, 0)
        self.keys[key] = val
        current = self.root
        current.count += delta
        for c in key:
            current = current.children[c]
            current.count += delta

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

[joemonkeylee]

代码

    public class MapSum
    {
        Dictionary<string, int> dictionary;

        public MapSum()
        {
            dictionary = new Dictionary<string, int>();
        }

        public void Insert(string key, int val)
        {
            if (dictionary.ContainsKey(key))
            {
                dictionary[key] = val;
            }
            else
            {
                dictionary.Add(key, val);
            }
        }

        public int Sum(string prefix)
        {
            int res = 0;
            foreach (KeyValuePair<string, int> pair in dictionary)
            {
                if (pair.Key.StartsWith(prefix))
                {
                    res += pair.Value;
                }
            }
            return res;
        }
    }

[Lydia61]

677. 简直映射

思路

哈希表

代码

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:
        res = 0
        for key,val in self.map.items():
            if key.startswith(prefix):
                res += val
        return res

复杂度分析

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

[kangliqi1]

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

}

[Jetery]

class MapSum {
public:
    static const int N = 3010;
    int son[N][26];
    int idx;
    int cnt[N];
    unordered_map<string, int> M;
    MapSum() {
        idx = 0;
        memset(cnt, 0, sizeof cnt);
        memset(son, 0, sizeof son);
    }

    void insert(string key, int val) {
        int p = 0;
        for(int i = 0; i < key.size(); i++){
            int u = key[i] - 'a';
            if (!son[p][u]) son[p][u] = ++idx;
            p = son[p][u];
            if (M.count(key)) cnt[p] += (val - M[key]);
            else cnt[p] += val;            
        }
        M[key] = val;
    }

    int sum(string prefix) {
        int p = 0;
        for(int i = 0; i < prefix.size(); i++){
            int u = prefix[i] - 'a';
            if (!son[p][u]) return 0;
            p = son[p][u];
        }
        return cnt[p];
    }
};

[lp1506947671]

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

复杂度分析

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