899. Prefix Value Sums
A seed bank records a yield score for each plant code. Build the class PrefixValueSums with an empty constructor.
insert(key, value)assignsvalueto the lowercase stringkey. Ifkeywas inserted before, its old value is replaced by the new one (it is not added to it).prefixTotal(prefix)returns the total of the current values of all keys that start withprefix; a key counts for its own full text as a prefix. If no key starts withprefix, return 0.
Values may be negative. Both operations must take time proportional to the length of their string argument, never to the number of keys stored.
Example 1
- Input:
- operations = ["PrefixValueSums","insert","insert","prefixTotal","insert","prefixTotal","prefixTotal","prefixTotal"]arguments = [[],["orchid",8],["orbit",5],["or"],["orchid",1],["or"],["orc"],["x"]]
- Output:
- [null,null,null,13,null,6,1,0]
- Explanation:
Both keys start with
or(8+5=13); re-insertingorchidreplaces its value 8 by 1, so the total becomes 6.
Example 2
- Input:
- operations = ["PrefixValueSums","insert","insert","prefixTotal","prefixTotal","prefixTotal"]arguments = [[],["lamp",-4],["lampshade",10],["lamp"],["lampsh"],["lampshades"]]
- Output:
- [null,null,null,6,10,0]
- Explanation:
The key
lampitself counts for the prefixlamp(-4+10=6); a prefix longer than every key sums to 0.
Constraints
1 ≤ key.length, prefix.length ≤ 50
-1000 ≤ value ≤ 1000
Strings contain lowercase English letters only; at most 2000 calls.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Input
- Each case is an operation log.
operationsnames the class first and then each method call;argumentsholds the arguments for each, in the same order. Your answer is one list with a result per operation -nullfor the constructor and for methods that return nothing.
Expected complexity
- Time
- O(L) per call
- Space
- O(total key characters)