KV Prefix Store
MediumTrie · Snowflake
Simulate a key-value store that starts empty. operations is a list of commands, processed in order:
["put", key, value]stores integervalueunder stringkey, replacing any existing value for that key.["delete", key]removeskeyif it is present; deleting a missing key does nothing.["prefix", p]returns every key currently in the store that starts with the stringp(the empty string matches every key), as[key, value]pairs sorted by key in ascending lexicographic order.
Return a list containing the result of each prefix command, in the order the commands appear. put and delete produce no output.
Example 1
- Input:
- operations = [["put", "apple", 3], ["put", "app", 1], ["put", "banana", 7], ["prefix", "app"], ["delete", "app"], ["put", "apple", 5], ["prefix", "a"], ["prefix", ""]]
- Output:
- [[["app", 1], ["apple", 3]], [["apple", 5]], [["apple", 5], ["banana", 7]]]
- Explanation
- The first scan finds
appandapple, sorted by key. Thenappis deleted andappleis overwritten with 5, soamatches onlyapple. The empty prefix matches every key.
Example 2
- Input:
- operations = [["prefix", "x"], ["put", "xy", 2], ["delete", "zz"], ["prefix", "xyz"]]
- Output:
- [[], []]
- Explanation
- The store is empty for the first scan. Later,
xyis shorter than the prefixxyz, so it does not start with it. Deleting the missing keyzzis ignored.
Constraints
- 0 ≤
operations.length≤ 105 - Keys are non-empty strings of lowercase English letters with length at most 20
- Values are integers
- The total number of rows returned by all
prefixcommands is at most 105