# LEETCODE 208. Implement Trie (Prefix Tree) 解题思路分析

Trie trie = new Trie();

`trie.insert("apple");trie.search("apple"); // 返回 truetrie.search("app"); // 返回 falsetrie.startsWith("app"); // 返回 truetrie.insert("app");trie.search("app"); // 返回 true`

• 你可以假设所有的输入都是由小写字母 `a-z` 构成的。
• 保证所有输入均为非空字符串。

Trie被称为前缀树，也叫做字典树，它是一个经典的树形结构。既然是树形结构，那么就少不了节点，对于字典树的节点我们可以定义为：

```class Node{
// 是否存在以当前节点结尾的单词
boolean isWord;
// 当前节点的后续字符
Node[] children = new Node[26];
}```

```class Node{
boolean isWord;
Node[] children = new Node[26];
}

Node root = new Node();
/** Initialize your data structure here. */
public Trie() {

}

/** Inserts a word into the trie. */
public void insert(String word) {
Node node = root;
char[] arr = word.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) children[c-'a'] = new Node();
node=children[c-'a'];
}
node.isWord=true;
}

/** Returns if the word is in the trie. */
public boolean search(String word) {
Node node = root;
char[] arr = word.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) return false;
node=children[c-'a'];
}
return node.isWord;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
Node node = root;
char[] arr = prefix.toCharArray();
for(char c : arr){
Node[] children = node.children;
if(children[c-'a']==null) return false;
node=children[c-'a'];
}
return true;
}```

Runtime: 29 ms, faster than 98.16% of Java online submissions for Implement Trie (Prefix Tree).

Memory Usage: 50.3 MB, less than 100.00% of Java online submissions for Implement Trie (Prefix Tree).