208. Implement Trie (Prefix Tree)

 1 class Trie {
 2 
 3     private TrieNode root;
 4     public Trie() {
 5         root = new TrieNode();
 6     }
 7     
 8     public void insert(String word) {
 9         TrieNode node = root;
10         for (int i = 0; i < word.length(); i++) {
11             char c = word.charAt(i);
12             if(node.children[c - ‘a‘] == null)
13                 node.children[c - ‘a‘] = new TrieNode();
14             node = node.children[c - ‘a‘];
15         }
16         node.isWord = true;
17     }
18     
19     public boolean search(String word) {
20         TrieNode ws = root;
21         for (int i = 0; i < word.length(); i++) {
22             char c = word.charAt(i);
23             if(ws.children[c - ‘a‘] == null)
24                 return false;
25             ws = ws.children[c - ‘a‘];
26         }
27         return ws.isWord;
28     }
29     
30     public boolean startsWith(String prefix) {
31         TrieNode ws = root;
32         for (int i = 0; i < prefix.length(); i++) {
33             char c = prefix.charAt(i);
34             if(ws.children[c - ‘a‘] == null)
35                 return false;
36             ws = ws.children[c - ‘a‘];
37         }
38         return true;
39     }
40 }
41 
42 class TrieNode {
43     public boolean isWord;
44     public TrieNode[] children = new TrieNode[26];
45 }
46 
47 /**
48  * Your Trie object will be instantiated and called as such:
49  * Trie obj = new Trie();
50  * obj.insert(word);
51  * boolean param_2 = obj.search(word);
52  * boolean param_3 = obj.startsWith(prefix);
53  */