实现 Trie（前缀树）：ACM 模式刷题
按标准输入读取测试数据，输出结果后可在 CodeACM 在线运行和提交。
题目描述
Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
· Trie() 初始化前缀树对象。
· void insert(String word) 向前缀树中插入字符串 word 。
· boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
· boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
输入格式
第一行输入操作数 q。
接下来 q 行为 insert word、search word 或 startsWith prefix。
输出格式
每个 search 和 startsWith 操作输出一行 true 或 false；insert 不输出。
数据范围
- 1 ≤ q ≤ 3 × 10⁴
- 单词和前缀仅包含小写英文字母且长度不超过 2000
公开样例
样例 1
输入
6 insert apple search apple search app startsWith app insert app search app
输出
true false true true
插入 app 前，它只是前缀而不是完整单词。
样例 2
输入
3 insert cat startsWith ca search car
输出
true false
存在 ca 前缀，但不存在完整单词 car。
练习建议
先根据输入输出格式写出可运行程序，再用公开样例检查结果；遇到边界情况时，补充自测用例后提交。