题目描述：
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
示例:
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 true
trie.search(“app”); // 返回 false
trie.startsWith(“app”); // 返回 true
trie.insert(“app”);
trie.search(“app”); // 返回 true
说明:
你可以假设所有的输入都是由小写字母 a-z 构成的。
保证所有输入均为非空字符串。
首先一个Trie下有26个子孩子，childen
TrieNode类下有一个val，然后是一个childen里面有26个孩子
class Trie {/** Initialize your data structure here. */TrieNode root = new TrieNode();/** Inserts a word into the trie. */public void insert(String word) {TrieNode wa = root;char [] cha = word.toCharArray();for (int i = 0; i < cha.length; i++) {int num = cha[i] - 'a';if(wa.childen[num] == null){wa.childen[num] = new TrieNode(cha[i]);}wa = wa.childen[num];if(i == cha.length - 1){wa.isWord = true;break;}}}/** Returns if the word is in the trie. */public boolean search(String word) {char cha[] = word.toCharArray();TrieNode node = root;for (int i = 0; i < cha.length; i++) {int num = (int)(cha[i] - 'a');if(node.childen[num] == null){return false;}else {node = node.childen[num];}}return node.isWord;}/** Returns if there is any word in the trie that starts with the given prefix. */public boolean startsWith(String prefix) {char cha[] = prefix.toCharArray();TrieNode node = root;for (int i = 0; i < cha.length; i++) {int num = (int)(cha[i] - 'a');if(node.childen[num] == null){return false;}else {node = node.childen[num];}}return true;}
}
class TrieNode{char val;boolean isWord;TrieNode [] childen = new TrieNode[26];public TrieNode() {}TrieNode(char c){TrieNode node = new TrieNode();node.val = c;}}