如何看待trie中的空间角色

Question

例如，我想插入"几个"；在trie中，但我不知道如何做到：

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

我得到这个错误：

线程中的异常"主"；java.lang.ArrayIndexOutOfBoundsException：索引-65超出长度29 的界限

数组的长度等于29。

我该如何解决这个问题？

Answer 1

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

相反，您可以在一个常量字符串的帮助下定义从字符到索引的转换：

private static final String ALPHABET = "abcdefghijklmnopqrstuvwxyz ";

注意z后面的空格。如果你想支持逗号、点等其他字符，你可以添加更多的字符。。。大写字母。。。等等。但是，此字符串的长度不应大于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];