Monday, February 23, 2015

TRIE implementation in Java

I have covered the fundamentals of trie in this post.

/**
 * TRIE implementation in Java 
 * Tries are general search tree where every node
 * can have some pre-defined number of children. Length of children is 26. Max
 * depth of trie is equal to max length of the word in the dictionary
 *
 * Constraints: 1. assume that all words are lowercase (uppercase letters are
 * converted to lowercase) 2. accept only a-z letters—no punctuation, no
 * hyphens, no accents, etc
 * 
 * Main Operations supported: 1. addword(..) : add a word to the dictionary 2.
 * search(..) : check if the given word exists in dictionary
 *
 * @author Siddheshwar
 */
public class Trie {
 private Node root;

 public Trie() {
  root = new Node();
 }

 /**
  * adds a dictionary word to the vocabolary or dictionary
  * 
  * @param word
  */
 public void addWord(String word) {
  if (word == null || !word.matches("[a-zA-Z]+")) { // or matches ("\\w+")
   return;
  }

  Node r = root;
  int index;
  for (char c : word.toLowerCase().toCharArray()) {
   index = this.getIndex(c);

   if (!r.hasChildAt(index)) {
    r = r.addChild(c);
   } else {
    r = r.getChildAt(index);
   }
  }
  r.setAsLeaf();
 }

 /**
  * Get index where the character will get mapped in the array 'a'/'A' will
  * be mapped to 0th, 'z'/'Z' will get mapped to 25th index
  * 
  * @param ch
  * @return index
  */
 private int getIndex(char ch) {
  // return (int)(ch - 'a');
  return String.valueOf(ch).codePointAt(0)
    - String.valueOf('a').codePointAt(0);
 }

 /**
  * Is word present in the trie
  * 
  * @param word
  * @return
  */
 public boolean contains(String word) {
  if (word == null)
   return true;
  Node r = root;
  for (char c : word.toCharArray()) {
   r = r.getChildAt(this.getIndex(c));
   if (r == null) {
    return false;
   }
  }
  return true;
 }

 /**
  * Returns the node (or null if word is not found)
  * 
  * @param word
  * @return Node
  */
 public Node getNodeEndingWithWord(String word) {
  if (word == null)
   return null;
  Node r = root;
  for (char c : word.toCharArray()) {
   r = r.getChildAt(this.getIndex(c));
   if (r == null) {
    return null;
   }
  }
  return r;
 }
}

import java.util.Arrays;
import java.util.List;

/**
 * Vertex or Node of a TRIE tree. Supports only alphabets a-z (ignores case) 'a'
 * occupies 0th position and 'z', 25th in Node array(i.e. children)
 */
public class Node {
 private Node[] childen;
 private boolean leaf;
 private char value;
 static final char NULL_CHAR = '\0';

 public Node() {
  childen = new Node[26];
  leaf = false;
  value = NULL_CHAR;
 }

 public Node(char c) {
  childen = new Node[26];
  leaf = false;
  value = c;
 }

 public List<Node> getChilden() {
  return Arrays.asList(childen);
 }

 public boolean hasChildAt(int index) {
  return this.childen[index] == null ? false : true;
 }

 public boolean isLeaf() {
  return leaf;
 }

 public char getValue() {
  return value;
 }

 public Node getChildAt(int index) {
  return this.childen[index];
 }

 public void setAsLeaf() {
  this.leaf = true;
 }

 public boolean isCharValid() {
  return this.value != NULL_CHAR ? true : false;
 }

 /**
  * add a child node to the current node
  * 
  * @param ch
  * @return Node
  */
 public Node addChild(char ch) {
  Node childNode = new Node(ch);
  // int index = (int)(ch - 'a'); prefer below approach
  int index = String.valueOf(ch).codePointAt(0)
    - String.valueOf('a').codePointAt(0);
  this.childen[index] = childNode;
  return childNode;
 }

 /**
  * Get count of valid children; upper limit is 26.
  * 
  * @return count
  */
 public int getChildrenCount() {
  int count = 0;
  for (int i = 0; i < 26; i++) {
   if (this.hasChildAt(i)) {
    count++;
   }
  }
  return count;
 }

 /**
  * Returns comma separated list of children for the node
  * 
  * @return
  */
 public String getChildren() {
  StringBuilder output = new StringBuilder();
  for (int i = 0; i < 26; i++) {
   if (this.hasChildAt(i)) {
    output.append((char) (i + 65)).append(",");
   }
  }
  return output.substring(0, output.length() - 1);
 }
}

2 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. package trie;

    import java.util.Objects;

    public class Trie {
    static final int ALPHABET_SIZE = 26;
    TrieNode root;

    Trie(){
    root = new TrieNode();
    }

    static class TrieNode {
    TrieNode[] children;

    boolean isEndOfWord; // mark end of word

    TrieNode(){
    this.children = new TrieNode[ALPHABET_SIZE];
    this.isEndOfWord = false;
    }
    }

    public void insert(String key){
    if(Objects.isNull(key) || key.length() ==0 ){
    return;
    }

    int index;
    TrieNode r = root;
    for(char ch : key.toCharArray()){
    index = ch - 'a';
    if(Objects.isNull(r.children[index])){
    r.children[index] = new TrieNode();
    }
    r = r.children[index];
    }

    r.isEndOfWord = true;
    }

    public boolean search(String key){
    if(Objects.isNull(key) || key.length() == 0){
    return true;
    }

    TrieNode r = root;
    int index;
    for(char ch : key.toCharArray()){
    index = ch - 'a';
    if(Objects.isNull(r.children[index])){
    return false;
    }
    r = r.children[index];
    }
    return Objects.nonNull(r) && r.isEndOfWord;
    }
    }

    ReplyDelete