首页 文章

如何正确检查trie中是否存在单词的前缀？

提问于
浏览 次
1

目前我的Trie类的“searchPrefix”功能定义如下：

public Boolean searchPrefix(String word) {
    TrieNode temp = this.root;
    for(int i = 0; i < word.length(); i++){
        if(temp.children.get(word.charAt(i)) == null) return false;
        else temp = temp.children.get(word.charAt(i));
    }
    return (temp.children.isEmpty()) ? false : true;
}

当输入字符串是trie对象内部存在的单词的前缀时，该函数应返回“true” . 以下是TrieNode类供参考：

class TrieNode {
   Character c;
   Boolean isWord = false;
   HashMap<Character, TrieNode> children = new HashMap<>();

   public TrieNode() {}
   public TrieNode(Character c) {
    this.c = c;
   }
}

根据这个在线评判，我错误地确定给定的输入字符串是否是前缀 . 任何人都可以解释为什么这是一个不正确的方法？我的想法是，当我们到达作为输入字符串结尾的节点时，如果节点有子节点，则它是其他单词的前缀，因此我们返回true . 然而，这显然是不正确的 .

java trie

1 回答

  • 1

    我认为你没有处理前缀是trie中的终结词的情况 .

    例如，假设trie中只有一个单词 hello . 对于 searchPrefix("hello") ，您的实现将返回false .

    要解决此问题，您还需要检查 isWord 标志：

    public Boolean searchPrefix(String word) {
    TrieNode temp = this.root;
    for (int i = 0; i < word.length(); i++){
        TrieNode next = temp.children.get(word.charAt(i));
        if (next == null) {
            return false;
        }
        temp = next;
    }
    return !temp.children.isEmpty() || temp.isWord;
}
    回复于

相关问题