Leetcode 677. Map Sum Pairs
1 min readJul 30, 2021
[medium]
Implement the MapSum
class:
MapSum()
Initializes theMapSum
object.void insert(String key, int val)
Inserts thekey-val
pair into the map. If thekey
already existed, the originalkey-value
pair will be overridden to the new one.int sum(string prefix)
Returns the sum of all the pairs' value whosekey
starts with theprefix
.
Example 1:
Input
["MapSum", "insert", "sum", "insert", "sum"]
[[], ["apple", 3], ["ap"], ["app", 2], ["ap"]]
Output
[null, null, 3, null, 5]Explanation
MapSum mapSum = new MapSum();
mapSum.insert("apple", 3);
mapSum.sum("ap"); // return 3 (apple = 3)
mapSum.insert("app", 2);
mapSum.sum("ap"); // return 5 (apple + app = 3 + 2 = 5)
Constraints:
1 <= key.length, prefix.length <= 50
key
andprefix
consist of only lowercase English letters.1 <= val <= 1000
- At most
50
calls will be made toinsert
andsum
.
[Java- map]
- use hashmap to store key String and the value
- use function: startsWith to check the prefix
- if String in the hashmap start with prefix, add them into the total count
[Use Trie datastructure]
- use TireNode to