LWC 50：677. Map Sum Pairs

LWC 50：677. Map Sum Pairs

传送门：677. Map Sum Pairs

Problem:

Implement a MapSum class with insert, and sum methods.

For the method insert, you’ll be given a pair of (string, integer). The string represents the key and the integer represents the value. If the key already existed, then the original key-value pair will be overridden to the new one.

For the method sum, you’ll be given a string representing the prefix, and you need to return the sum of all the pairs’ value whose key starts with the prefix.

Example 1:

Input: insert(“apple”, 3), Output: Null
Input: sum(“ap”), Output: 3
Input: insert(“app”, 2), Output: Null
Input: sum(“ap”), Output: 5

两种做法，在插入时，记入所有前缀，查询快。第二种做法为插入时直接记录，查询时计算所有前缀， 插入快。

插入O(n)查询O(1)

class MapSum {

    /** Initialize your data structure here. */
    Map<String, Integer> mem;
    Map<String, Integer> set;
    public MapSum() {
        mem = new HashMap<>();
        set = new HashMap<>();
    }

    public void insert(String key, int val) {
        if (!set.containsKey(key)){
            set.put(key, val);
            for (int i = 0; i <= key.length(); ++i){
                String sub = key.substring(0, i);
                mem.put(sub,mem.getOrDefault(sub, 0) + val);
            }            
        }else{
            int cnt = set.get(key);
            for (int i = 0; i <= key.length(); ++i){
                String sub = key.substring(0, i);
                mem.put(sub, mem.get(sub) - cnt + val);
            }
        }
    }

    public int sum(String prefix) {
        if (!mem.containsKey(prefix)) return 0;
        return mem.get(prefix);
    }
}

插入O(1)查询O(n)

class MapSum {
    /** Initialize your data structure here. */
    Map<String, Integer> mem;

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

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

    public int sum(String prefix) {
        int sum = 0;
        for (String pre : mem.keySet()) {
            for (int i = 0; i <= pre.length(); ++i) {
                if (prefix.equals(pre.substring(0, i))) {
                    sum += mem.get(pre);
                }
            }
        }
        return sum;
    }
}

当然你还可以使用Trie来维护前缀，代码如下：

class MapSum {

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

    TrieNode build(TrieNode root, String key, int val) {
        char[] cs = key.toCharArray();
        if (root == null) root = new TrieNode();
        TrieNode cur = root;
        cur.val = val;
        for (char c : cs) {
            if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new TrieNode();
            cur = cur.children[c - 'a'];
            cur.val += val;
        }
        return root;
    }

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

    Map<String, Integer> mem;
    TrieNode root;
    public MapSum() {
        mem = new HashMap<>();
        root = null;
    }

    public void insert(String key, int val) {
        if (!mem.containsKey(key)) {
            root = build(root, key, val);
            mem.put(key, val);
        }
        else {
            int sub = mem.get(key);
            root = build(root, key, val - sub);
            mem.put(key, val);
        }
    }

    public int sum(String prefix) {
        return search(root, prefix);
    }
}