Trie
LC #208Medium
Implement Trie (Prefix Tree)
Trie
AmazonGoogleMetaMicrosoftBloombergProblem
Implement a trie with insert, search (exact), and startsWith (prefix) operations.
triedesignstring
Constraints
- ›1 ≤ word.length, prefix.length ≤ 2000
- ›Lowercase English letters only
- ›At most 3 × 10⁴ calls total
Example
Input
insert("apple"), search("apple"), search("app"), startsWith("app"), insert("app"), search("app")Output
true, false, true, trueWhy
"apple" inserted → search exact match returns true; "app" not inserted yet → false; startsWith always checks prefix