89. Implement Trie — Insert, Search, Prefix
Store words in a structure that can distinguish complete words from prefixes of longer words. An exact search succeeds only for an inserted complete word; a prefix search succeeds when an inserted word begins with that prefix.
Repeated insertion is idempotent. Empty words and empty prefixes have specific, different behavior described in the contract.
Example 1
Input
insert("apple"); search("apple"); search("app"); startsWith("app")Output
true, false, true
Explanation: The app path exists, but it is not a complete word until inserted.
Example 2
Input
search(""); startsWith(""); insert(""); search("")Output
false, true, true
Explanation: The root exists initially; its terminal flag is initially false.
Constraints
0 <= word.length, prefix.length <= 10000 <= operation count <= 104- Words and prefixes contain only lowercase English letters.
Hints
Hint 1
Words with a common prefix can share work.
Hint 2
What marks that a word ends before its path does?
Hint 3
Store child edges and a terminal flag; insert allocates, queries only walk.
Submissions
Your recent submissions for this problem.
Checking sign-in…
Discussion
Ask a question or share an approach. Posts are public; avoid personal information and mark solution spoilers clearly.
No discussion yet. Start the conversation with a question about this problem.
Checking sign-in…
Run your code to check the sample cases, or submit it to check the full validation suite.
Prefix versus complete word
[["insert","apple"],["search","app"],["startsWith","app"],["insert","app"],["search","app"]]
[null,false,true,null,true]