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
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]][null, null, true, false, true, null, true]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].
["Trie", "insert", "insert", "search", "startsWith", "startsWith", "search", "insert", "search"]
[[], ["code"], ["coder"], ["code"], ["co"], ["cope"], ["cope"], ["cope"], ["cope"]][null, null, null, true, true, false, false, null, true]After inserting code and coder, search("code") is true and startsWith("co") is true. The word cope is absent at first, so startsWith("cope") and search("cope") are false. After insert("cope"), the final search("cope") is true, so the output is [null, null, null, true, true, false, false, null, true].
["Trie", "insert", "insert", "insert", "search", "search", "startsWith", "startsWith", "search"]
[[], ["cat"], ["car"], ["dog"], ["cow"], ["dog"], ["ca"], ["doe"], ["doe"]][null, null, null, null, false, true, true, false, false]After inserting cat, car, and dog, search("cow") is false because cow was never inserted, while search("dog") is true. The prefix ca exists, but doe was never inserted and is not a stored prefix, so startsWith("doe") and search("doe") are both false.
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.