CODEWITHSUNDEEP
javadata-structurestrie
Louis B
Louis B

Reputation: 342

Trying to implement a trie data structure in java

I am trying to make a TrieNode class. Every node has a letter, links(the other nodes it connects to), a boolean declaring if this node marks the end of a full word, and I am trying to add another boolean saying weather it is part of a valid prefix. The part I am having trouble with is the prefix part. I am trying to make an isValidPrefix method.

My TrieNode class:

class TrieNode
{
    char letter;
    TrieNode[] links;
    boolean fullWord;
    boolean validPrefix;

    TrieNode(char letter)
    {
        this.letter = letter;
        links = new TrieNode[26];
        for(int i=0;i<26;i++){//i keep getting a nullPointer exception
            this.links[i].validPrefix=false;
        }
        this.fullWord = false;
        this.validPrefix=true;
    }
}

In my add method, every time I add a node, I set that nodes validPrefix to true.

My is valid prefix method:

 public boolean isValidPrefix(TrieNode root, String word) {
    int length = word.length();
    char[] letters = word.toCharArray();
    TrieNode curNode = root;
    for (int i = 0; i < length; i++){
        curNode = curNode.links[letters[i]-97];
    }
    return curNode.validPrefix;//get a nullPointerException
}

Here is my add method for reference 

    public void insertWord(TrieNode root, String word){//97 is ascii value
    int length = word.length();
    char[] letters = word.toCharArray();
    TrieNode curNode = root;

    for (int i = 0; i < length; i++){
        if (curNode.links[letters[i]-97] == null)
            curNode.links[letters[i]-97] = new TrieNode(letters[i]);
        curNode = curNode.links[letters[i]-97];
        curNode.validPrefix=true;
    }
    curNode.fullWord = true;  
}

Upvotes: 0

Views: 1541

Answers (2)

Louis B
Louis B

Reputation: 342

i figured it out, i just check if the node is null or not:

public static boolean isValidPrefix(TrieNode root, String word){
    int length = word.length();
    char[] letters = word.toCharArray();
    for (int i = 0; i < length; i++){
        root = root.links[letters[i]-97];
    }
    if(root==null)
        return false;
    return true;
}

Upvotes: 0

Kanagavelu Sugumar
Kanagavelu Sugumar

Reputation: 19260

The root TrieNode[] links is instantiated with new TrieNode[26]; but those 26 are not assigned with valid object.
How about the below?

for(int i=0;i<26;i++){
         TrieNode obj = new TrieNode();
                  obj.validPrefix=false;
        this.links[i] = obj;
    }

Upvotes: 1

Related Questions