This blog will soon be merged with

JavaByPatel

which explains each solution in detail, to visit new blog, click JavaByPatel

Wednesday, 24 December 2014

Trie Data Structure Dictionary Example

package miscellaneous;

class TrieNode{
 private char character;
 private TrieNode[] series = new TrieNode[26];
 private boolean isEnding;

 public TrieNode(char character, boolean isEnding) {
  this.character = character;
  this.isEnding = isEnding;
 }

 public char getCharacter() {
  return character;
 }
 public void setCharacter(char character) {
  this.character = character;
 }
 public TrieNode[] getSeries() {
  return series;
 }
 public void setSeries(TrieNode[] series) {
  this.series = series;
 }
 public boolean isEnding() {
  return isEnding;
 }
 public void setEnding(boolean isEnding) {
  this.isEnding = isEnding;
 }

}
package miscellaneous;

public class TrieDictionary {

 private TrieNode rootNode = new TrieNode('\0', false);

 public static void main(String[] args) {
  new TrieDictionary();
 }
 public TrieDictionary() {
  String[] str = {"hell", "hello", "well"};
  for (int i = 0; i < str.length; i++) {
   storeWordsInDictionary(str[i], rootNode);
   //System.out.println();
  }

  System.out.println(checkWordExist("all"));
  System.out.println();
  printAllWordsOfDictionary(rootNode.getSeries(), 0, "");

 }

 private void printAllWordsOfDictionary(TrieNode[] arr, int index, String str) {
  if(arr==null)
   return;

  for (int i = 0; i < arr.length; i++) {
   if(arr[i]!=null){
    printAllWordsOfDictionary(arr[i].getSeries(), 0, str+arr[i].getCharacter());
    if(arr[i].isEnding()){
     System.out.println(str+arr[i].getCharacter());
    }
   }  
  }
 }

 private void storeWordsInDictionary(String word, TrieNode startNode){

  for (int i = 0; i < word.length(); i++) {
   char c = word.charAt(i);
   if(startNode.getSeries()[c-97]==null){
    startNode.getSeries()[c-97] = new TrieNode(c, (i==word.length()-1)?true:false);
    startNode = startNode.getSeries()[c-97];
   }else{
    startNode = startNode.getSeries()[c-97]; 
    if(i==word.length()-1){
     startNode.setEnding(true);
    }
   }
  } 
 }

 private boolean checkWordExist(String word){
  for (int i = 0; i < word.length(); i++) {
   char c = word.charAt(i);

   if(rootNode.getSeries()[c-97]==null){
    return false;
   }else{
    rootNode = rootNode.getSeries()[c-97];
    if(i==word.length()-1){
     if(rootNode.isEnding()!=true){
      return false;
     }
    }
   }
  }

  return true;
 }

}


No comments:

Post a Comment