TRIE

TRIE

  August 06, 2017    

---

Explanation :

We used to insert character by character as  a tree so that we can traverse it more quickly.
here we created a hashmap having character and its tree child node.

 

Applications :

Telephone Dictonary

Word Search
Faster Searching using prefix

  


Code:

import java.util.*;
import java.lang.*;
import java.io.*;
class trie
{
    HashMap<Character,trie> children=new HashMap<Character,trie>();
    boolean isCompleteWord=false;
    public HashMap<Character, trie> getChildren() {
        return children;
    }

    public void setChildren(HashMap<Character, trie> children) {
        this.children = children;
    }

    public boolean isCompleteWord() {
        return isCompleteWord;
    }

    public void setCompleteWord(boolean completeWord) {
        isCompleteWord = completeWord;
    }


}
class trieSolnMain
 {
     public static trie getNode()
     {
         trie a=new trie();
         return a;
     }
     public static  void insert(trie root,char[] st)
     {
         trie child =null;
         trie cur=root;
         for(int i=0;i<st.length;i++)
         {
             if(cur.getChildren().get(st[i])==null)
             child = getNode();
             else
             child=cur.getChildren().get(st[i]);
             cur.getChildren().put(st[i], child);
             if(i==st.length-1)
             cur.setCompleteWord(true);
             cur=child;
         }
     }
     public static int search(char[] st,trie root)
     {
         trie cur=root;
         trie prev=root;
         for(int i=0;i<st.length;i++)
         {
             if(cur.getChildren().get(st[i])==null)
             return 0;
             prev=cur;
          cur=cur.getChildren().get(st[i]); 
          
         }
         return (prev.isCompleteWord())?1:0;
     }
public static void main (String[] args)
{
Scanner ab=new Scanner(System.in);
int t=ab.nextInt();
while(t-->0)
{
   int n=ab.nextInt();
   trie r=new trie();
   trie root=getNode();
   String arr[]=new String[n];
   for(int i=0;i<n;i++)
   {
       arr[i]=ab.next();
      insert(root,arr[i].toCharArray());
       
   }
   System.out.println(search(ab.next().toCharArray(),root));
 
}
}
}