insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters
a-z. class TrieNode {
// Initialize your data structure here.
public TrieNode() {
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
}
// Returns if the word is in the trie.
public boolean search(String word) {
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
Naive Thinking: At first I didn't know Trie. Here is the definition from Wikipedia. https://en.wikipedia.org/?title=Trie
The structure was given. Only need to fill in the methods. The structure tell me that each node is described as TrieNode. And the whole trie is just referred by its root. Thus, a TrieNode should contain children TrieNode attributes in order to have access to every TrieNode in the tree via root TrieNode.
The search() method and startwith() method differs in that the last character must be an ending TrieNode in search() while startwith() doesn't have to be.
Below is my implementation. I use HashMap to maintain children TrieNode relationship.
class TrieNode {
// Initialize your data structure here.
public String data;
public Map<Character, TrieNode> children;
public boolean isEnd;
public TrieNode() {
data = new String();
children = new HashMap<Character, TrieNode>();
isEnd = false;
}
public TrieNode(String s){
data = s;
children = new HashMap<Character, TrieNode>();
isEnd = false;
}
}
public class Trie {
private TrieNode root;
public Trie() {
root = new TrieNode();
}
// Inserts a word into the trie.
public void insert(String word) {
TrieNode cur = root;
for(int i = 0;i < word.length();i++){
if(cur.children.containsKey(word.charAt(i))){
cur = cur.children.get(word.charAt(i));
}else{
String s = root.data + word.charAt(i);
TrieNode child = new TrieNode(s);
cur.children.put(word.charAt(i), child);
cur = child;
}
}
cur.isEnd = true;
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode cur = root;
for(int i = 0;i < word.length();i++){
if(cur.children.containsKey(word.charAt(i)))
cur = cur.children.get(word.charAt(i));
else
return false;
}
return cur.isEnd;
}
// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode cur = root;
for(int i = 0;i < prefix.length();i++){
if(cur.children.containsKey(prefix.charAt(i)))
cur = cur.children.get(prefix.charAt(i));
else
return false;
}
return true;
}
}
