Implement Trie
Medium · Tries · Trie · Hash Table · String · Design
Problem
Build a prefix tree over lowercase words:
- insert(word) — add a word
- search(word) — was this exact word inserted?
- startsWith(prefix) — was any inserted word beginning with this prefix?
Tests replay a call sequence: the first entry names the class, each later entry is a method with its arguments, and calls returning nothing report None.
Examples
Input: insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")
Output: True, False, True, then True"app" is a prefix of "apple" but was not itself inserted — until it is.
Constraints
- 1 <= len(word), len(prefix) <= 2000
- Lowercase English letters only
- Up to 3 * 10^4 calls
Approaches
- A set of words plus a set of prefixes — time O(1) per query, space O(total characters²)
Related problems
Start free on Cariara · Coding problems · System design studio
