1. class Trie {
    3.     /** Initialize your data structure here. */
    4.     private Trie[] dict;
    5.     private boolean isEnd;
    7.     public Trie() {
    8.         dict = new Trie[26];
    9.         isEnd = false;
    10.     }
    12.     /** Inserts a word into the trie. */
    13.     public void insert(String word) {
    14.         Trie node = this;
    15.         for(int i = 0; i < word.length(); i++) {
    16.             int index = word.charAt(i) - 'a';
    17.             if(node.dict[index] == null) {
    18.                 node.dict[index] = new Trie();
    19.             }
    20.             node = node.dict[index];
    21.         }
    22.         node.isEnd = true;
    23.     }
    25.     /** Returns if the word is in the trie. */
    26.     public boolean search(String word) {
    27.         Trie node = searchPrefix(word);
    28.         // if(node != null && node.isEnd) {
    29.         //     return true;
    30.         // }
    31.         // return false;
    32.         return node != null && node.isEnd;
    34.     }
    36.     /** Returns if there is any word in the trie that starts with the given prefix. */
    37.     public boolean startsWith(String prefix) {
    38.          return searchPrefix(prefix) != null;
    39.     }
    41.     public Trie searchPrefix(String word) {
    42.         Trie node = this;
    43.         for(int i = 0; i < word.length(); i++) {
    44.             int index = word.charAt(i) - 'a';
    45.             if(node.dict[index] == null) {
    46.                 return null;
    47.             }
    48.             node = node.dict[index];
    49.         }
    50.         return node;
    51.     }
    52. }
    54. /**
    55.  * Your Trie object will be instantiated and called as such:
    56.  * Trie obj = new Trie();
    57.  * obj.insert(word);
    58.  * boolean param_2 = obj.search(word);
    59.  * boolean param_3 = obj.startsWith(prefix);
    60.  */