4

我是 java 新手，我想创建一个非常简单的“单词完成”程序。我将阅读字典文件并递归地将单词添加到节点数组（大小为 26）中。我相信我已经成功地做到了这一点，但我不知道如何通过和打印比赛。为了测试，我现在只是通过调用函数来插入 2 个单词。一旦一切正常，我将添加读取文件并从单词中删除垃圾的方法。

例如：如果“test”和“tester”这两个词在树内，用户输入“tes”，它应该显示“test”和“tester”。

如果有人能告诉我如何通过和打印比赛（如果有的话），我将非常感激。完整代码如下。

谢谢

4

2 回答 2

3

您实施的称为 "trie"。您可能想查看现有的实现。

您用来存储子节点的东西称为哈希表，您可能希望使用标准实现并避免自己实现它，除非您有非常非常具体的理由这样做。您的实现有一些限制（例如字符范围）。

我认为，您的代码在方法中有一个错误has：

...
else if (letter[val].flag==true || word.length()==1) {
    return true;
}

如果该方法打算在字符串以wordthen 开头的情况下返回 true，则不应检查flag. 如果仅在完全匹配的情况下必须返回 true，则不应检查word.length().

最后，解决您的问题：不是最佳但最简单的解决方案是创建一个方法，该方法接受一个字符串并返回一个与该字符串匹配的节点以及一个由节点中的所有单词组成的方法。像这样的东西（未经测试）：

class Tree {

    ...
    public List<String> matches(CharSequence prefix) {
        List<String> result = new ArrayList<>();
        if(r != null) {
            Node n = r._match(prefix, 0);
            if(n != null) {
                StringBuilder p = new StringBuilder();
                p.append(prefix);
                n._addWords(p, result);
            }
        }
        return result;
    }
}

class Node {

    ...
    protected Node _match(CharSequence prefix, int index) {
        assert index <= prefix.length();
        if(index == prefix.length()) {
            return this;
        }
        int val = prefix.charAt(index) - 'a';
        assert val >= 0 && val < letter.length;
        if (letter[val] != null) {
            return letter[val].match(prefix, index+1);
        }
        return null;
    }

    protected void _addWords(StringBuilder prefix, List<String> result) {
        if(this.flag) {
            result.add(prefix.toString());
        }    
        for(int i = 0; i<letter.length; i++) {
            if(letter[i] != null) {
                prefix.append((char)(i + 'a'));
                letter[i]._addWords(prefix, result);
                prefix.delete(prefix.length() - 1, prefix.length());
            }
        }
    }
}
于 2013-04-16T08:10:58.350 回答
-1

也许这里有点远，但你为什么不在这里尝试正则表达式呢？据我了解，您希望将单词与单词列表匹配：

List<String> getMatches(List<String> list, String regex) {

  Pattern p = Pattern.compile(regex);
  ArrayList<String> matches = new ArrayList<String>();

  for (String s:list) {
    if (p.matcher(s).matches()) {
      matches.add(s);
    }
  }

  return matches
}
于 2013-04-16T07:20:55.930 回答