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));
}
}
}
}
1 Answer 1
TrieContainer[26]
contains a magic number. Since we can calculate with char
I'd write TrieContainer['Z' - 'A' + 1]
to make it clear.
I'd use System.out.printf("\n%b", isWordPresent(start, "abcd"))
rather than string concatenation System.out.println("\n"+isWordPresent(start, "abcd")).
I'd let if
follow by a space to distinguish it from method invocations (as you do it with for
). I'd also surround else
with spaces.
You're inconsistent in surrounding operators with spaces or not. Do the former.
I'd rename isFound
to isWordFound
.
Since the variables character
are just local to for
I'd call them just ch.
character-97
can be replaced with ch - 'a'
then.
Array indices can be char,
too. So:
for (int i = 0; i < start.series.length; i++) {
...
... (char)(97+i));
... can be changed to:
for (char ch = 0; ch < start.series.length; ch++) {
...
... (ch + 'a'));
I think start
isn't an ideal name. With this if(start.isEnd)
looks somehow irritating.
Having just static
methods in Trie
and public
variables in TrieContainer
doesn't look well-designed.