java - 从 TRIE 数据结构检索字符串时数组索引超出范围？

Question

我将字符串及其频率存储在 TRIE 数据结构中

hello 100
world 5000
good 2000
bad 9000

下面是我的 TrieImpl 类

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
    }
}

下面是我的 TrieNode 类 -

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();
    }
}

我能够在 TRIE 中插入字符串及其频率，并且还能够查找已经存在的给定字符串的频率。现在我面临的问题是 - 如果我查找 TRIE 中不存在的字符串，它会抛出 Arrays Index Out of Range 错误。

如果你看到我上面的 TrieImpl 类，我正在搜索 TRIE 中不存在的字符串 HELLO1，因此对于这种情况，它会抛出 ArrayIndex 超出范围。

有什么想法可以解决这个问题吗？

Answer 1

您应该简单地检查 val 是否超出 getFreq 函数中的范围。

您可能还需要检查目标索引处是否确实有一个元素(即它不是 null)。

此外，正如另一个答案中所指出的，您将“无效”字符串传递给函数，因为 1 会导致负 val 值/索引- 要么您应该避免这样做，要么您也可以将该检查添加到您的函数中。

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