class Trie {
class TrieNode{
Map<Character,TrieNode> children = new HashMap<>();
boolean isLeaf;
}
private TrieNode root;
/** Initialize your data structure here. */
public Trie() {
root= new TrieNode();
}
/** Inserts a word into the trie. */
public void insert(String word) {
TrieNode node = root;
for(char c : word.toCharArray()){
if(!node.children.containsKey(c)){

node.children.put(c,new TrieNode());
}
node = node.children.get(c);
}
node.isLeaf= true;
}
/** Returns if the word is in the trie. */
public boolean search(String word) {
TrieNode p = root;
for(char c : word.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return p.isLeaf;
}

/** Returns if there is any word in the trie that starts with the given prefix. */
public boolean startsWith(String prefix) {
TrieNode p = root;
for(char c : prefix.toCharArray()) {
if(!p.children.containsKey(c)) {
return false;
}
p = p.children.get(c);
}
return true;
}
}

--

--