Saturday, 8 July 2017

Implementation of Trie in Java

//*******************************************************************
// Dear CompileJava users,
//
// CompileJava has been operating since 2013 completely free. If you
// find this site useful, or would otherwise like to contribute, then
// please consider a donation (link in 'More Info' tab) to support
// development of the new CompileJava website (stay tuned!).
//
// Most sincerely, Z.
//*******************************************************************
import java.lang.Math; // headers MUST be above the first class
import java.util.*;
// one class needs to have a main() method
public class Trie
{
  private TrieNode root;
 
  public Trie(){
    root = new TrieNode((char)0);
  }
 
  public void insert(String word){
   
    int l = word.length();
   
    TrieNode crawl = root;
   
    for(int i=0;i<l;i++){
      HashMap<Character,TrieNode> child = crawl.getChildren();
      char ch = word.charAt(i);
      if(child.containsKey(ch)){
        crawl = child.get(ch);
      }else{
        TrieNode temp = new TrieNode(ch);
        child.put(ch,temp);
        crawl = temp;
      }
    }
   
    crawl.setIsEnd(true);
  }
   
  public boolean search(String word){
    int l = word.length();
   
    TrieNode crawl = root;
   
    for(int i=0;i<l;i++){
      HashMap<Character,TrieNode> child = crawl.getChildren();
      char ch = word.charAt(i);
      if(!child.containsKey(ch)){
        return(false);
      }else{
        crawl = child.get(ch);
      }
    }
   
    return((crawl!=null)&&(crawl.getIsEnd()));
  }
 
  public static void main(String[] args)
  {
    String []array = {"the", "a", "there", "answer", "any","by", "bye", "their"};
   
    Trie trie = new Trie();
    for(int i=0;i<array.length;i++){
      trie.insert(array[i]);
    }
   
    System.out.println(trie.search("the"));
    System.out.println(trie.search("these"));
    System.out.println(trie.search("their"));
    System.out.println(trie.search("thaw"));
  }
}
class TrieNode{
 
  private char value;
  private HashMap<Character,TrieNode> children;
  private boolean isEnd;
 
  public TrieNode(char ch){
    value = ch;
    children = new HashMap<Character,TrieNode>();
    isEnd = false;
  }
 
  public char getValue(){return(value);}
  public HashMap<Character,TrieNode> getChildren(){return(children);}
  public void setIsEnd(boolean isEnd){
    this.isEnd = isEnd;
  }
 
  public boolean getIsEnd(){return(isEnd);}
}

No comments:

Post a Comment