使用 trie 时我得到一个不应该出现的异常错误

Question

我正在开发一个简单的拼写检查器，它从文本文件中抓取字母表，然后使用 trie 来检查任何单词是否拼写正确

代码

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.util.*;

public class Spellchecker {
static final int ALPHABET_SIZE = 26;

static class node {

    node[] children = new node[ALPHABET_SIZE];
    boolean isEndOfWord;

    node() {
        isEndOfWord = false;
        for (int i = 0; i < ALPHABET_SIZE; i++)
            children[i] = null;
    }
}

static node root;

static void insert(String key) {
    int length = key.length();


    node pCrawl = root;

    for (int level = 0; level < length; level++) {
        int index = key.charAt(level) - 'a';
        if (pCrawl.children[index] == null)
            pCrawl.children[index] = new node();

        pCrawl = pCrawl.children[index];
    }

    // mark last node as leaf
    pCrawl.isEndOfWord = true;
}

static int wordCount (node root){
    int result = 0;

    if (root.isEndOfWord){
        result++;

    }
    for (int i = 0; i < ALPHABET_SIZE; i ++){
        if (root.children[i]!=null){
            result += wordCount(root.children[i]);
        }
    }
    return result;
}


// Returns true if key presents in trie, else false
static boolean search(String key) {
    int length = key.length();
    node pCrawl = root;

    for (int level = 0; level < length; level++) {
        int index = key.charAt(level) - 'a';

        if (pCrawl.children[index] == null)
            return false;

        pCrawl = pCrawl.children[index];
    }

    return (pCrawl != null && pCrawl.isEndOfWord);
}


public static void main(String args[]) throws IOException {

    ArrayList<String> dictionary = new ArrayList<>();
    ArrayList<String> text = new ArrayList<>();

    try (BufferedReader br = new BufferedReader(new FileReader("dictionary.txt"))) {
        while (br.ready()) {
            dictionary.add(br.readLine());
        }
    } catch (Exception e) {
        e.printStackTrace();
    }

        root = new node();

        
        int i;
        for (i = 0; i < dictionary.size(); i++)
            insert(dictionary.get(i));

       
            if (!search(){
                System.out.println("not in dictionary: " + text.get(j));
            }
        }
    }
}

我得到的错误非常令人困惑

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index -65 out of bounds for length 26
    at ASS1.Spellchecker.search(Spellchecker.java:67)
    at ASS1.Spellchecker.main(Spellchecker.java:126)

我完全不知道它怎么可能 -65。任何帮助将不胜感激。

Answer 1

根据你的代码和错误，我认为你的search键里面有一个space字符，所以space字符ASCII码是32，所以搜索时

int index = key.charAt(level) - 'a';
//key.charAt(level) = space = 32
//index = 32 - 'a' = 32 - 97 = -65 //invalid index

最好的解决方案是，如果您的输入不是全是小写英文字母，那么最好使用 HashMap 来保存 children 而不是 array。

使用 trie 时我得到一个不应该出现的异常错误

when using a trie i get an unusual error that shouldnt be possible

java

spell-checking

trie