尝试执行

Question

我试图在Java中实现一个非常简单的Trie，该Trie支持3种操作。我希望它具有一个insert方法，一个has方法（即trie中的某个单词）和一个toString方法以字符串形式返回trie。我相信我的插入工作正常，但是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个子级的根。尝试插入时，将在该根节点上调用insert，该根节点将在正确的位置递归创建一个新节点，并一直持续到单词完成为止。我相信该方法可以正常工作。

我有功能非常坏了，因为我 有
到有return语句括号出于某种原因之外。我不能将其包含在else子句中，否则编译器会抱怨。除此之外，我认为该方法应该进行一些调整，但我无法终生解决。

toString是我尝试解决的野兽，但是我扔给它的任何东西都没有用，所以我将其保留下来，直到解决问题。如果我有工作，我也许可以找到一种将其重新格式化为toString函数的方法。

int val的用途= word.charAt（0）-64;
是因为输入的每个字符串都必须全部大写（之后将创建一个字符串格式化函数以确保做到这一点），因此第一个字母的int值-64将是其在数组中的位置。也就是说，数组索引0为A，因此A
= 64，A-64 =0。B= 65，B-64 = 1，依此类推。

Answer 1

您的has函数应该看起来像这样：

if (c[val]!=null && word.length()>1) {
    return c[val].has(word.substring(1)); //<-- Change is on this line
} else if (c[val].flag==true && word.length()==1) {
    ...etc

您执行递归调用，但是您确实需要让该值传播回原始调用者。