# Question

Formatted question description: https://leetcode.ca/all/208.html

208	Implement Trie (Prefix Tree)

Implement a trie with methods
insert
search
startsWith

Note:
You may assume that all inputs are consist of lowercase letters a-z.

@tag-trie


# Algorithm

Each node of the alphabetic dictionary tree defines an array of child node pointers with a size of 26, and then uses a marker to record whether it is a word up to the current position.

When initializing, the 26 child nodes are all empty.

Then the insert operation only needs to calculate the position of each character of the string to be inserted, and then find out whether this child node exists, if it does not exist, create a new one, and then move to the next one.

The word search and prefix search operations are very similar to the insert operation. The difference is that if there are no child nodes, false is returned. At the end of the search time, you need to look at the flag, and you can directly return true when you search the prefix.

Java