Trie

 1	class TrieNode {
 2	    public char c;
 3	    public boolean isEnd;
 4	    public TrieNode[] children;
 5	
 6	    public TrieNode(char c){
 7	        this.c = c;
 8	        isEnd = false;
 9	        children = new TrieNode[26];
10	    }
11	}
12	
13
14	class Trie {
15	    public TrieNode root;
16	
17	    public Trie(){
18	        root = new TrieNode(' ');
19	    }
20	
21	    //insert
22	    public void insert(String s){
23	        TrieNode cur = root;
24	        for (char ch : s.toCharArray()){
25	            if (cur.children[ch - 'a'] == null){
26	                cur.children[ch - 'a'] = new TrieNode(ch);
27	            }
28	            cur = cur.children[ch - 'a'];
29	        }
30	        cur.isEnd = true;
31	    }
32	
33	    public boolean search(String s){
34	        TrieNode cur = root;
35	        for (char ch : s.toCharArray()){
36	            if (cur.children[ch - 'a'] == null){
37	                return false;
38	            }
39	            cur = cur.children[ch - 'a'];
40	        }
41	        return cur.isEnd;
42	    }
43	
44	    public boolean prefix(String s){
45	        TrieNode cur = root;
46	        for (char ch : s.toCharArray()){
47	            if (cur.children[ch - 'a'] == null){
48	                return false;
49	            }
50	            cur = cur.children[ch - 'a'];
51	        }
52	        return true;
53	    }
54	}