# ---
# title: 208. Implement Trie (Prefix Tree)
# id: problem208
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Design, Trie
# link: <https://leetcode.com/problems/implement-trie-prefix-tree/description/>
# hidden: true
# ---
# 
# Implement a trie with `insert`, `search`, and `startsWith` methods.
# 
# **Example:**
# 
#     
#     
#     Trie trie = new Trie();
#     
#     trie.insert("apple");
#     trie.search("apple");   // returns true
#     trie.search("app");     // returns false
#     trie.startsWith("app"); // returns true
#     trie.insert("app");   
#     trie.search("app");     // returns true
#     
# 
# **Note:**
# 
#   * You may assume that all inputs are consist of lowercase letters `a-z`.
#   * All inputs are guaranteed to be non-empty strings.
# 
# 
## @lc code=start
using LeetCode

## add your code here:
## @lc code=end
