leetcode-677-Map-Sum-Pairs

发表于   |  

描述

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:

1
2
3
4
Input: insert("apple", 3), Output: Null
Input: sum("ap"), Output: 3
Input: insert("app", 2), Output: Null
Input: sum("ap"), Output: 5

分析

这个一个应用前缀树的很好的例子。

解决方案1(Java)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class MapSum {
    HashMap<String, Integer> map;
    TrieNode root;
    
    public MapSum() {
        map = new HashMap();
        root = new TrieNode();
    }
    
    public void insert(String key, int val) {
        int delta = val - map.getOrDefault(key, 0);
        map.put(key, val);
        TrieNode current = root;
        current.score += delta;
        for (char c: key.toCharArray()) {
            current.children.putIfAbsent(c, new TrieNode());
            current = current.children.get(c);
            current.score += delta;
        }
    }
    
    public int sum(String prefix) {
        TrieNode current = root;
        for (char c: prefix.toCharArray()) {
            current = current.children.get(c);
            if (current == null) {
                return 0;
            }
        }
        return current.score;
    }
}

class TrieNode {
    Map<Character, TrieNode> children = new HashMap();
    int score;
}

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

题目来源