我试图在Java中实现一个非常简单的Trie,支持3个操作 . 我希望它有一个insert方法,一个has方法(即trie中的某个单词),以及一个以字符串形式返回trie的toString方法 . 我相信我的插入工作正常,但是并且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个子节点的根 . 尝试插入时,将在该根节点上调用insert,该节点以正确的位置递归创建新节点,并继续直到该单词完成 . 我相信这种方法运作正常 .
我的函数非常破碎,因为出于某种原因我必须在括号外面有返回语句 . 我不能在else子句中包含它或编译器抱怨 . 除此之外,我认为这种方法应该有一些调整,但我无法弄清楚我的生活 .
toString是一个我试图解决的野兽,但我没有投入任何东西,所以我会离开它,直到我解决了问题 . 如果我开始工作,我可能想办法将其重新格式化为toString函数 .
int val = word.charAt(0) - 64的目的;是因为输入的每个字符串必须全部大写(我将创建一个字符串格式化函数以确保此后)所以第一个字母的int值 - 64将是它在数组中的位置 . 即,数组索引0是A,所以A = 64,A = 64 = 0. B = 65,B = 64 = 1,依此类推 .
6 回答
您的
has
函数应该如下所示:您执行递归调用,但您确实需要让该值传播回原始调用者 .
也许您可以使用“Map c”而不是“TrieNode [] c”,这将允许您将此用于所有类型的字符大写/小写甚至特殊字符,甚至可以节省空间(在26处分配26个字符数组)每个角色级别)
这是我的实施: -
在这里我的实施:
This Trie Map实现has (called get in this implementation)和toString
这是简单的java实现,不使用任何其他数据结构