245. Implement a Trie (Prefix Tree)

Medium · Design

Implement a Trie with insert, search, and startsWith methods. A trie (prefix tree) is a tree data structure for storing strings where nodes share common prefixes.

Examples

Example 1
Input: insert("apple"); search("apple")→true; search("app")→false; startsWith("app")→true
Output: [true,false,true]

Constraints

• 1 ≤ word.length ≤ 2000, lowercase English letters only