3つの操作をサポートする非常に単純なTrieをJavaで実装しようとしています。insertメソッド、hasメソッド（つまり、トライ内の特定の単語）、および文字列形式でトライを返すtoStringメソッドが必要です。挿入は適切に機能していると思いますが、hasとtoStringは難しいことがわかっています。これが私がこれまでに持っているものです。
トライクラス。
public class CaseInsensitiveTrie implements SimpleTrie {
//root node
private TrieNode r;
public CaseInsensitiveTrie() {
r = new TrieNode();
}
public boolean has(String word) throws InvalidArgumentUosException {
return r.has(word);
}
public void insert(String word) throws InvalidArgumentUosException {
r.insert(word);
}
public String toString() {
return r.toString();
}
public static void main(String[] args) {
CaseInsensitiveTrie t = new CaseInsensitiveTrie();
System.out.println("Testing some strings");
t.insert("TEST");
t.insert("TATTER");
System.out.println(t.has("TEST"));
}
}
そしてノードクラス
public class TrieNode {
//make child nodes
private TrieNode[] c;
//flag for end of word
private boolean flag = false;
public TrieNode() {
c = new TrieNode[26]; //1 for each letter in alphabet
}
protected void insert(String word) {
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 word length > 1, then word is not finished being added.
//otherwise, set the flag to true so we know a word ends there.
if (word.length() > 1) {
c[val].insert(word.substring(1));
} else {
c[val].flag = true;
}
}
public boolean has(String word) {
int val = word.charAt(0) - 64;
if (c[val]!=null && word.length()>1) {
c[val].has(word.substring(1));
} else if (c[val].flag==true && word.length()==1) {
return true;
}
return false;
}
public String toString() {
return "";
}
}
したがって、基本的に、Trieを作成する場合、TrieNodeは26の子を持つルートとして作成されます。挿入が試行されると、そのルートノードで挿入が呼び出され、正しい位置に新しいノードが再帰的に作成され、単語が完了するまで続行されます。メソッドは正しく機能していると思います。
何らかの理由で括弧の外にreturnステートメントが必要なため、私のhas関数は非常に壊れています。else句に含めることができないか、コンパイラが文句を言います。それ以外は、少し調整すればうまくいくと思いますが、一生理解できません。
toStringは私が取り組もうとした獣ですが、何も投げないので、問題が解決するまでそのままにしておきます。動作するようになれば、それをtoString関数に再フォーマットする方法を見つけることができるかもしれません。
int val = word.charAt（0）-64;の目的 入力する各文字列はすべて大文字でなければならないため（後でこれを確実にするために文字列フォーマット関数を作成します）、最初の文字のint値-64が配列内の位置になります。つまり、配列インデックス0はAであるため、A = 64、A-64 =0です。B=65、B-64=1などです。