Implementing a Trie in Java

Question

I've implemented the Trie data structure in Java but am not getting the correct answer when I'm running the code. I've built the trie using some simple strings. I'm then searching for words and prefixes but the result is not proper. I've tried debugging it a lot but still can't find where it might be wrong.

Trie.java:

public class Trie {

    public class Vertex {
        public int words;
        public int prefixes;
        public Vertex edges[] = new Vertex[26];

        public Vertex() {
            this.words = 0;
            this.prefixes = 0;
        }
    }

    private Vertex root;

    Trie() {
        this.root = new Vertex();
    }

    private void addWord(Vertex vertex, String word) {
        if (word.isEmpty()) {
            vertex.words++;
        } else {
            vertex.prefixes++;
            int indexOfNextChar = (int) word.charAt(0) - 97;
            vertex.edges[indexOfNextChar] = new Vertex();
            this.addWord(vertex.edges[indexOfNextChar], word.substring(1));
        }
    }

    private int countWords(Vertex vertex, String word) {
        if (!word.isEmpty()) {
            int indexOfNextChar = (int) word.charAt(0) - 97;
            if (vertex.edges[indexOfNextChar] == null) {
                return 0;
            } else {
                return this.countWords(vertex.edges[indexOfNextChar], word.substring(1));
            }
        } else {
            return vertex.words;
        }
    }

    private int countPrefixes(Vertex vertex, String word) {
        if (!word.isEmpty()) {
            int indexOfNextChar = (int) word.charAt(0) - 97;
            if (vertex.edges[indexOfNextChar] == null) {
                return 0;
            } else {
                return this.countPrefixes(vertex.edges[indexOfNextChar], word.substring(1));
            }
        } else {
            return vertex.prefixes;
        }
    }

    public void addWord(String word) {
        this.addWord(this.root, word.toLowerCase());
    }

    public int countPrefixes(String word) {
        if (word.length() != 0) {
            return this.countPrefixes(this.root, word.toLowerCase());
        }
        return -1;
    }

    public int countWords(String word) {
        if (word.length() != 0) {
            return this.countWords(this.root, word.toLowerCase());
        }
        return -1;
    }
}

TrieTester.java

public class TrieTester {
    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.addWord("Ayush");
        trie.addWord("Ayur");
        trie.addWord("Ayub");
        trie.addWord("Ayan");
        trie.addWord("Bhushan");

        // Should output 0, outputs 0
        System.out.println("Count of word Ayus: " + trie.countWords("Ayus"));

        // Should output 1, outputs 0
        System.out.println("Count of word Ayush: " + trie.countWords("Ayush"));

        // Should output 4, outputs 1
        System.err.println("Count of prefix Ay: " + trie.countPrefixes("Ay"));
    }
}

I referred to the Topcoder Trie tutorial to implement this.

I'd start testing with 1-character strings, then 2-character strings, and inspect the complete state of the trie. — 9000
– 9000, Commented Apr 19, 2017 at 19:44
Step through with a debugger, and watch the edge cases closely. Especially watch out when you create a new Vertex.. you need to reuse them after you have created the first one. — Chris K
– Chris K, Commented Apr 19, 2017 at 19:46

kraskevich · Accepted Answer · 2017-04-19 20:38:51Z

The else clause in the addWord method is definitely incorrect (there might be other bugs, too):

vertex.prefixes++;
int indexOfNextChar = (int) word.charAt(0) - 97;
vertex.edges[indexOfNextChar] = new Vertex();
this.addWord(vertex.edges[indexOfNextChar], word.substring(1));

Your code always creates a new vertex. That's wrong. You should do it if and only if there's no edge for the given character yet. That is, it should be like:

if (vertex.edges[indexOfNextChar] == null) {
    vertex.edges[indexOfNextChar] = new Vertex();
}

There are a few other issues with your implementation. For instance, the String.substring method works in linear time so adding a string to a trie requires quadratic time. You can fix that by iterating over all characters of the word instead of making a recursive for its substrings. Elimination recursion is also a good idea because you can run into stack overflow error for longer strings.

Collectives™ on Stack Overflow

Implementing a Trie in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related