1import java.util.HashMap;
2import java.util.Map;
3
4class TrieNode {
5    private Map<Character, TrieNode> children;
6    private boolean isEndOfWord;
7
8    public TrieNode() {
9        children = new HashMap<>();
10        isEndOfWord = false;
11    }
12
13    public boolean isEndOfWord() {
14        return isEndOfWord;
15    }
16
17    public void setEndOfWord(boolean endOfWord) {
18        isEndOfWord = endOfWord;
19    }
20
21    public TrieNode getChild(char ch) {
22        return children.get(ch);
23    }
24
25    public void addChild(char ch) {
26        children.put(ch, new TrieNode());
27    }
28}
29
30public class Trie {
31    private TrieNode root;
32
33    public Trie() {
34        root = new TrieNode();
35    }
36
37    public void insert(String word) {
38        TrieNode current = root;
39        for (int i = 0; i < word.length(); i++) {
40            char ch = word.charAt(i);
41            TrieNode node = current.getChild(ch);
42            if (node == null) {
43                current.addChild(ch);
44                node = current.getChild(ch);
45            }
46            current = node;
47        }
48        current.setEndOfWord(true);
49    }
50
51    public boolean search(String word) {
52        TrieNode current = root;
53        for (int i = 0; i < word.length(); i++) {
54            char ch = word.charAt(i);
55            TrieNode node = current.getChild(ch);
56            if (node == null) {
57                return false;
58            }
59            current = node;
60        }
61        return current.isEndOfWord();
62    }
63
64    public boolean startsWith(String prefix) {
65        TrieNode current = root;
66        for (int i = 0; i < prefix.length(); i++) {
67            char ch = prefix.charAt(i);
68            TrieNode node = current.getChild(ch);
69            if (node == null) {
70                return false;
71            }
72            current = node;
73        }
74        return true;
75    }
76
77    public static void main(String[] args) {
78        Trie trie = new Trie();
79        trie.insert("apple");
80        trie.insert("banana");
81
82        System.out.println(trie.search("apple")); // true
83        System.out.println(trie.search("banana")); // true
84        System.out.println(trie.search("orange")); // false
85
86        System.out.println(trie.startsWith("app")); // true
87        System.out.println(trie.startsWith("ban")); // true
88        System.out.println(trie.startsWith("ora")); // false
89    }
90}