Build a trie where each node accumulates the sum of values for all words passing through it.

Map Sum Pairs

medium

Acceptance: 47%

TrieHash TableDesign

Design a key-value map where keys are strings and values are integers. It must support two operations: insert(key, val) associates the key with the given value (overwriting any previous value), and sum(prefix) returns the total of all values whose keys start with the given prefix.

Examples

Example 1:

Input:MapSum(), insert('tree', 5), sum('tr'), insert('treat', 3), sum('tr')

Output:[null,null,5,null,8]

Hints

1234567

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // Write your solution here
    }
}

Map Sum Pairs

Examples

Hints

Related Problems