Description
A trie (pronounced as 'try') or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. Implement the Trie class with insert, search, and startsWith methods. Return the result as an array.
Examples
Input:
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]Output:
[null, null, true, false, true, null, true]Explanation:
After inserting "apple", searching for "apple" returns true, searching for "app" returns false, and startsWith("app") returns true, so the result is [null, null, true, false, true, null, true].
Input:
TrieinsertinsertsearchstartsWithstartsWithsearchinsertsearchOutput:
[null,true,false]Explanation:
After the trie operations complete, the result is [null,true,false].
Input:
TrieinsertinsertinsertsearchsearchstartsWithstartsWithsearchOutput:
[null,true]Explanation:
After inserting the word, searching for the exact word returns true, so the result is [null,true].
Constraints
- •
1 ≤ word.length, prefix.length ≤ 2000 - •
word and prefix consist only of lowercase English letters. - •
At most 3 × 10⁴ calls will be made to insert, search, and startsWith.