prefixTree
VibhishanRoy
59
Interview

class Trie {
//head point for tree
private Node root;
//inner class to store node of tree
class Node{
public char c;
public boolean isWord;
public Node[] child;
public Node(char c)
{
this.c=c;
isWord=false;
child=new Node[26];
}
}

public Trie() {
    root=new Node('\0');
}
//insert funcion
public void insert(String word) {
    Node curr=root;
    for(int i=0;i<word.length();i++)
    {
        char c=word.charAt(i);
        if(curr.child[c-'a']==null)
            curr.child[c-'a']=new Node(c);
        curr=curr.child[c-'a'];
    }
    curr.isWord=true;
    
}

//search for given string
public boolean search(String word) {
Node node=getNode(word);
//if node is present and word is there
//then it will return true
return node!=null&&node.isWord;

}
// check if given start word is there or not
public boolean startsWith(String prefix) {
    return getNode(prefix)!=null;
    
}
//function for getNode with given word
private Node getNode(String word)
{
    Node curr=root;
    for(int i=0;i<word.length();i++)
    {
      char c=word.charAt(i) ;
          if(curr.child[c-'a']==null) return null;
        curr=curr.child[c-'a'];
    }
    return curr;
}

}

/**

  • Your Trie object will be instantiated and called as such:
  • Trie obj = new Trie();
  • obj.insert(word);
  • boolean param_2 = obj.search(word);
  • boolean param_3 = obj.startsWith(prefix);
    */
Comments (0)
No comments yet.