Implement a trie with
insert, search, and startsWith methods.
Note:
You may assume that all inputs are consist of lowercase letters
You may assume that all inputs are consist of lowercase letters
a-z.
Answer:
class TrieNode {
// Initialize your data structure here.
public char c;
//important!
public boolean isEnd;
public int count;
public ArrayList<TrieNode> children;
public TrieNode(char cha) {
this.c = cha;
isEnd = false;
count = 1;
children = new ArrayList<TrieNode>();
}
//return the child node whose char == cha
public TrieNode rtnchildNode(char cha){
for(TrieNode child : this.children){
if(child.c == cha){
return child;
}
}
return null;
}
}
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;
TrieNode next = null;
for(int i=0;i< word.length(); ++i){
next = cur.rtnchildNode(word.charAt(i));
if(next!=null){
next.count++;
cur=next;
}else{
TrieNode insertNewNode = new TrieNode(word.charAt(i));
cur.children.add(insertNewNode);
cur=insertNewNode;
}
if(i== word.length()-1){
cur.isEnd = true;
}
}
}
// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode cur = root;
TrieNode next = null;
for(int i=0; i< word.length(); ++i){
next = cur.rtnchildNode(word.charAt(i));
if(next != null){
cur = next;
}else{
return false;
}
//important!Judge the tail char whether 'isEnd'
if(i == word.length()-1){
if(cur.isEnd == true){
return true;
}
}
}
return false;
}
// Returns if there is any word in the trie that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode cur = root;
TrieNode next = null;
for(int i=0; i< prefix.length(); ++i){
next = cur.rtnchildNode(prefix.charAt(i));
if(next != null){
cur = next;
}else{
return false;
}
}
return true;
}
}
// Your Trie object will be instantiated and called as such:
// Trie trie = new Trie();
// trie.insert("somestring");
// trie.search("key");
No comments:
Post a Comment