208. Implement Trie Prefix Tree

Practice Implement Trie Prefix Tree for free on NudgeCode: Medium, Binary Tree pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Build a trie (prefix tree) for lowercase words:

• insert(word) adds word.
• search(word) returns true if word was inserted before.
• startsWith(prefix) returns true if some inserted word starts with prefix.

Each test is a list of operations and their arguments; the expected output lists what each call returns (null for calls that return nothing).

Example

["Trie","insert","search","search","startsWith","insert","search"]
[[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
->  [null,null,true,false,true,null,true]

Constraints

• 1 <= word.length, prefix.length <= 2000
• Words and prefixes are lowercase English letters
• At most 3 * 10^4 calls in total