How do I consider a space character in a trie?

Question

For example, I want to insert "a few" in the trie, but I do not know how to do it:

public void insertWord(String wordName){
    for (int i = 0; i < wordName.length(); i++){
        if( current.children[wordName.charAt(i) - 'a'] == null)
            current.children[wordName.charAt(i) - 'a'] = new Node(wordName.charAt(i));
        current = current.children[wordName.charAt(i) - 'a'];
    }
}

I get this error:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -65 out of bounds for length 29

The length of array is equal to 29.

How can I solve this?

Answer 1

The problem is that you define the index for the children array with the expression wordName.charAt(i) - 'a'. But the ordinal value of a space is much smaller than that of 'a', so that becomes a negative value.

Instead, you could define the conversion from character to index with the help of a constant string:

private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz ";

Notice the space after the z. You could add more characters, if you want to support other characters like a comma, a point, ... capital letters, ...etc. But, the length of this string should not be greater than the length of the children array.

Then, in your function, you can use that string as follows:

    int key = ALPHABET.indexOf(wordName.charAt(i));
    if( current.children[key] == null)
        current.children[key] = new Node(wordName.charAt(i));
    current = current.children[key];