ceid-vg ceid-vg - 7 months ago 32
Java Question

Digital Tries (JAVA) - Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -13

So I was testing some codes from the Internet about Digital Tries for a project I have and I have stuck on this one because everything I try returns this error :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -13


This is where I found this code (Code Source)

TrieNode.java

class TrieNode {
TrieNode[] arr;
boolean isEnd;
// Initialize your data structure here.
public TrieNode() {
this.arr = new TrieNode[26];
}
}


Trie.java

public class Trie {
private TrieNode root;

public static void main(String[] args) {
Trie tr = new Trie();
tr.insert("TEST");
System.out.println("TEST " + tr.search("TEST"));
}

public Trie() {
root = new TrieNode();
}

// Inserts a word into the trie.
public void insert(String word) {
TrieNode p = root;
for(int i=0; i<word.length(); i++){
char c = word.charAt(i);
int index = c-'a';
if(p.arr[index]==null){
TrieNode temp = new TrieNode();
p.arr[index]=temp;
p = temp;
}else{
p=p.arr[index];
}
}
p.isEnd=true;
}

// Returns if the word is in the trie.
public boolean search(String word) {
TrieNode p = searchNode(word);
if(p==null){
return false;
}else{
if(p.isEnd)
return true;
}

return false;
}

// Returns if there is any word in the trie
// that starts with the given prefix.
public boolean startsWith(String prefix) {
TrieNode p = searchNode(prefix);
if(p==null){
return false;
}else{
return true;
}
}

public TrieNode searchNode(String s){
TrieNode p = root;
for(int i=0; i<s.length(); i++){
char c= s.charAt(i);
int index = c-'a';
if(p.arr[index]!=null){
p = p.arr[index];
}else{
return null;
}
}

if(p==root)
return null;

return p;
}
}


Output :

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -13
at Trie.insert(Trie.java:20)
at Trie.main(Trie.java:6)


To Compile :

javac TrieNode.java Trie.java
java Trie


Any Ideas to solve the issue?

Answer

int index = c - 'a' is working on the char 'T' during the first iteration of your for loop.

In terms of char values, 'T' - 'a' = -13, thus index = -13 which throws the exception when checking the array.

Edit:

Your solution isn't working because you're using capital letters. In the article, the program uses only 'a' through 'z'. You can easily change your code to accommodate this:

char c = Character.toLowerCase(word.charAt(i));