leetExpert
Practice

Implement Trie (Prefix Tree)

Module 20 · Tries

Problem

Implement a Trie class with three methods:

  • insert(word) — add word to the trie.
  • search(word) — return true if word was inserted (exactly), else false.
  • startsWith(prefix) — return true if any inserted word begins with prefix, else false.

Examples

Example 1

Inputinsert("apple"), search("apple")Outputtrue

Example 2

Inputsearch("app")Outputfalse

Explanation. "app" was never inserted as a word

Example 3

InputstartsWith("app")Outputtrue

Explanation. but apple starts with "app"

Example 4

Inputinsert("app"), search("app")Outputtrue

Explanation. now it has been

Constraints

words and prefixes are lowercase English letters, 1–2000 characters; up to 3·10⁴ calls total across the three methods.

Attempt it first

This is the concept lesson made into an interface — build it yourself before reading on. The one thing to get exactly right is the difference between search and startsWith: the search("app") → false line in the example above is the entire test. If your search returns true for "app" after only "apple" was inserted, you've forgotten the is_end_of_word flag. Write all three methods and trace that example by hand.