我如何考虑 trie 中的 space 字符？

Question

比如我想在trie中插入“a few”，但不知如何操作：

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'];
    }
}

我收到这个错误：

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

数组长度等于29

我该如何解决这个问题？

Answer 1

问题是您使用表达式 wordName.charAt(i) - 'a' 定义了 children 数组的索引。但是aspace的序数比'a'的序数小很多，所以变成了负值。

相反，您可以借助常量字符串定义从字符到索引的转换：

private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz ";

注意 z 之后的 space。如果您想支持其他字符，如逗号、点、...大写字母等，您可以添加更多字符。但是，这个字符串的长度不能大于children数组的长度。

然后，在您的函数中，您可以按如下方式使用该字符串：

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

我如何考虑 trie 中的 space 字符？

How do I consider a space character in a trie?

java

dictionary

trie