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);
}
}
This comment has been removed by the author.
ReplyDeletepackage trie;
ReplyDeleteimport 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;
}
}