6
\$\begingroup\$

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));
            }
        }
    }
}
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.