Array Index out of range while retrieving string from TRIE data structure?

Question

I am storing string and its frequencies in TRIE data structure

hello 100
world 5000
good 2000
bad 9000

Below is my TrieImpl class

public class TrieImpl {

    //root node
    private TrieNode r;

    public TrieImpl() {
        r = new TrieNode();
    }

    public int find(String word) {
        return r.getFreq(word);
    }

    public void insert(String word, int freq) {
        r.insert(word, freq);
    }

    public String toString() {
        return r.toString();
    }

    public static void main(String[] args) {

        TrieImpl t = new TrieImpl();

        System.out.println("Testing some strings");
        // storing strings and its frequencies
        t.insert("HELLO", 10);
        t.insert("WORLD", 20);

        System.out.println(t.find("HELLO"));
        System.out.println(t.find("HELLO1")); // this line throws Array Index Out of Range
    }
}

And below is my TrieNode class -

public class TrieNode {

    // make child nodes
    private TrieNode[] c;
    // flag for end of word
    private boolean flag = false;
    // stores frequency if flag is set
    private int frequency;

    public TrieNode() {
        c = new TrieNode[26];
    }

    protected void insert(String word, int frequency) {
        int val = word.charAt(0) - 64;

        // if the value of the child node at val is null, make a new node
        // there to represent the letter
        if (c[val] == null) {
            c[val] = new TrieNode();
        }

        // if the value of the child node at val is null, make a new nod
        if (word.length() > 1) {
            c[val].insert(word.substring(1), frequency);
        } else {
            c[val].flag = true;
            c[val].frequency = frequency;
        }
    }


    public int getFreq(String word) {
        int val = word.charAt(0) - 64;
        if (word.length() > 1) {
            return c[val].getFreq(word.substring(1));
        } else if (c[val].flag == true && word.length() == 1) {
            return c[val].frequency;
        } else
            return -1;
    }


    public String toString() {
    return c.toString();
    }
}

I am able to insert string and its frequencies in TRIE and also able to lookup frequencies for a give string which is already present. Now the issue which I am facing is - If I am looking up forr a string which is not there in the TRIE, it throws Arrays Index Out of Range error.

If you see my above TrieImpl class, I am searching for string HELLO1 which is not there in TRIE, so for that case, it throws out ArrayIndex out of range.

Any thoughts how to fix that?

Answer 1

You should simply check if val's going to be out of range in your getFreq function.

You probably also need to check if there's actually an element at the target index (i.e. it's not null).

Also, as pointed out in the other answer, you're passing an 'invalid' string to your function, because 1 results in a negative val value / index - either you should avoid doing this, or you could add that check to your function as well.

public int getFreq(String word) {
  int val = word.charAt(0) - 64;
  if (val < 0 || val >= c.length || c[val] == null)
    return -1;
  ...
}

Answer 2

You are using: t.find("HELLO1"), which will be passed to your getFreq() function.

it will proceed calling getFreq() with ELLO1, LLO1, LO1, O1

At the point, when the implementation retries it with only word 1 due due your recursive aproach, it will result in int val = word.charAt(0) - 64; // 49-64 and thats a value of val = -15 - and that's not a valid array index.