Prefix Registry
EasyTries & StringsFree
Problem
A search box keeps a registry of words. You receive its activity as a list of operations ops, each a pair [command, word]:
["insert", w] adds w to the registry. ["exact", w] asks whether w itself was inserted. ["prefix", p] asks whether any inserted word starts with p.
Process the operations in order and return the answers to the exact and prefix queries, in order. Inserts produce no output.
Example 1
- Input:
- ops = [["insert","apple"],["exact","apple"],["exact","app"],["prefix","app"],["insert","app"],["exact","app"]]
- Output:
- [true, false, true, true]
"app" is only a prefix until it is inserted on its own; after that the exact query succeeds.
Example 2
- Input:
- ops = [["prefix","a"],["insert","a"],["prefix","a"],["exact","a"]]
- Output:
- [false, true, true]
Constraints
- 1 ≤ ops.length ≤ 3·10^4
- 1 ≤ word.length ≤ 2000
- Words are lowercase English letters.
- Total characters across all operations ≤ 10^6.
Hint
Show the first hint
Words that share a beginning should share storage for that beginning.
Walkthrough
How to approach it
01Clarify before coding
- Can the same word be inserted twice? Yes; it changes nothing, the word is simply present.
- Is a word a prefix of itself? Yes: after inserting "cart", prefix "cart" is true.
- Only lowercase letters? Yes, so each node has at most 26 children.
02Brute force
Keep the words in a list; for each query scan every word and compare it, or check startsWith.
Cost: O(N·L) per query for N stored words of length L: with 3·10^4 operations this reaches billions of character comparisons.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.