I have implemented a trie data structure in my way, though it is very similar to what major implementations I found but would like to get it reviewed by experts.
I don't see the need to store character in TrieContainer
class as position within the series reflects the character stored. Maybe I am missing something and am wrong in my understanding.
Trie container
package trie;
public class TrieContainer{
public boolean isEnd;
public TrieContainer[] series = new TrieContainer[26];
}
Operations class
package trie;
public class Trie {
public static void main(String[] args) {
TrieContainer start = new TrieContainer();
storeWords(start, "abc");
storeWords(start, "abcd");
storeWords(start, "abcde");
storeWords(start, "india");
storeWords(start, "hello");
storeWords(start, "hell");
printWordStrings(start,"");
System.out.println("\n"+isWordPresent(start, "abcd"));
}
private static void storeWords(TrieContainer start, String word){
for (int j = 0; j < word.length(); j++) {
char character = word.charAt(j);
//In series, check the position of character,
//if it is already filled then check the series of filled Trie object.
//if it is not filled then create new TrieContainer object and place it at correct position, and check
//if it is end of the word, then mark isEnd = true or else false;
if(start.series[character-97]!=null){
if(word.length()-1 == j){ //if word is found till last character, then mark the end as true.
start.series[character-97].isEnd = true;
}
start = start.series[character-97];
}else{
TrieContainer trie = new TrieContainer();
trie.isEnd = (word.length()-1 == j ? true:false);
start.series[character-97] = trie;
start = start.series[character-97];
}
}
}
private static boolean isWordPresent(TrieContainer start, String word){
boolean isFound = true;
for (int i = 0; i < word.length(); i++) {
char character = word.charAt(i);
//if at character position TrieContainer object is present then character is found and
//start looking for next character is word.
if(start.series[character-97]!=null){
if(word.length()-1 != i){
start = start.series[character-97];
}else{
if(!start.series[character-97].isEnd){
isFound = false;
}
}
}else{
isFound = false;
break;
}
}
return isFound;
}
private static void printWordStrings(TrieContainer start, String toPrint) {
if(start==null){
return;
}
if(start.isEnd){
System.out.println(toPrint);
}
for (int i = 0; i < start.series.length; i++) {
TrieContainer t = start.series[i];
if(t!=null){
printWordStrings(t, toPrint + (char)(97+i));
}
}
}
}