medium

Implement Trie (Prefix Tree)

Implement a data structure storing lowercase words with three operations: insert(word), search(word) returning whether the exact word exists, and startsWith(prefix) returning whether any stored word begins with the prefix.

Constraints

1 ≤ word.length ≤ 2000
Lowercase English letters
At most 3 · 10^4 operations

Examples

in: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")

out: true, false, true, true

Code it yourself

Solve in

Your python code

Test execution is not yet available for this exercise.Practice journal →Draft saved in this browser.

Hints:

Which approach applies?

Choose an approach to check your pattern recognition, or reveal the discussion when you need help.